algorithm - 无法在O(n)时间内解决孤独数问题

This question already has answers here:

How to find the only number in an array that doesn't occur twice [duplicate]
（5个答案）
在给定的数字数组中，一个元素将显示一次，其余元素将显示两次。你能在o（n）线性时间内找到那个数吗？
例如-lonelyNumber([4, 4, 6, 1, 3, 1, 3]) // 6
到目前为止，我在javascript和我的代码中尝试这个-

var lonelyNumber=function(arr) {
  for(var i=0;i<arr.length;i++) {
    for(var j=0;j<arr.length;j++) {
      if(j!==i && arr[i]===arr[j]) {
        break;
      }
    }
    if(j===arr.length) {
      return arr[i];
    }
  }
}

console.log(lonelyNumber([4, 4, 6, 1, 3, 1, 3]));

但是这是O（n ^ 2）的复杂性。我怎么把它送到O（n）？

最佳答案

你可以用hashmap来做这个方法是在javascript中使用对象。
基本上，我循环遍历数组，如果第一次找到对象，则添加新的键；如果第二次找到对象，则删除键最后，对象中剩下的唯一键就是结果。

var lonelyNumber=function(arr) {
  var obj={};
  for(var i=0;i<arr.length;i++) {
    if(obj[arr[i]]) {
      delete obj[arr[i]];
    } else {
      obj[arr[i]]=true;
    }
  }
  return Object.keys(obj)[0];
}

这将导致O（n）的复杂性。