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

Question

在给定的数字数组中，一个元素将显示一次，其余元素将显示两次。你能在 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)？

标签： algorithmdata-structures

Answer 1

您可以为此使用哈希图。做到这一点的方法是在 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) 的复杂性。