40

在所有其他数字恰好出现两次的列表中查找仅出现一次的数字的最佳算法是什么。

所以，在整数列表中（让我们把它当作一个数组）每个整数都重复两次，除了一个。要找到那个，最好的算法是什么。

4

11 回答 11

137

最快 (O(n)) 和最节省内存 (O(1)) 的方法是使用 XOR 操作。

在 C 中：

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

这将打印“1”，这是唯一出现一次的。

这是有效的，因为第一次点击一个数字时，它会用自身标记 num 变量，而第二次它会用自身取消标记 num （或多或少）。唯一未标记的是您的非重复项。

于 2008-08-29T20:43:57.017 回答
19

顺便说一句，您可以扩展这个想法，以非常快速地在重复列表中找到两个唯一数字。

让我们称唯一的数字 a 和 b。正如凯尔建议的那样，首先对所有内容进行 XOR。我们得到的是a^b。我们知道 a^b != 0，因为 a != b。选择 a^b 的任何 1 位，并将其用作掩码 - 更详细地说：选择 x 作为 2 的幂，以便 x & (a^b) 不为零。

现在将列表分成两个子列表——一个子列表包含所有数字 y 且 y&x == 0，其余的进入另一个子列表。通过我们选择 x 的方式，我们知道 a 和 b 在不同的桶中。我们还知道每对重复项仍然在同一个桶中。所以我们现在可以对每个桶独立地应用你老的“XOR-em-all”技巧，并完全发现 a 和 b 是什么。

巴姆。

于 2008-08-29T21:31:05.640 回答
11

O(N) 时间，O(N) 内存

HT=哈希表

HT.clear() 按您看到的每个项目的顺序遍历列表

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

最后，HT 中的项目就是您要查找的项目。

注意（信用@Jared Updike）：该系统将找到所有 Odd 项目实例。

评论：我不明白人们如何投票支持给你 NLogN 性能的解决方案。在哪个宇宙中“更好”？我更震惊你将接受的答案标记为 NLogN 解决方案......

但是，我确实同意，如果内存需要保持不变，那么 NLogN 将是（到目前为止）最好的解决方案。

于 2008-08-29T20:08:56.290 回答
4

Kyle 的解决方案显然无法捕捉数据集不遵循规则的情况。如果所有数字都成对出现，算法将给出零结果，与零完全相同的值将是唯一出现一次的值。

如果有多个单次出现值或三元组，则结果也将是错误的。

测试数据集很可能最终会使用更昂贵的算法，无论是内存还是时间。

Csmba 的解决方案确实显示了一些错误数据（没有或不止一个出现值），但没有其他（四倍）。关于他的解决方案，根据 HT 的实现，内存和/或时间都超过 O(n)。

如果我们不能确定输入集的正确性，那么排序和计数或使用哈希表计数以整数本身作为哈希键的次数都是可行的。

于 2008-09-03T13:14:19.693 回答
1

我会说使用排序算法然后通过排序列表查找数字是一种很好的方法。

现在的问题是找到“最好的”排序算法。排序算法有很多，每种算法都有自己的优点和缺点，所以这是一个相当复杂的问题。维基百科条目似乎是一个很好的信息来源。

于 2008-08-29T20:11:31.743 回答
1

在 Ruby 中的实现：

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end
于 2014-09-14T15:17:00.160 回答
0

您需要指定“最佳”的含义 - 对某些人来说，速度是最重要的，并且会将答案限定为“最佳” - 对于其他人来说，如果解决方案更具可读性，他们可能会原谅几百毫秒。

除非您更具体，否则“最佳”是主观的。

那说：

遍历数字，为每个数字在列表中搜索该数字，当您到达搜索结果数量仅返回 1 的数字时，您就完成了。

于 2008-08-29T20:07:34.047 回答
0

似乎您能做的最好的事情就是遍历列表，对于每个项目，将其添加到“已见”项目列表中，或者如果它已经存在，则将其从“已见”列表中删除，最后您的“已见”列表" 项目将包括单数元素。这是时间方面的 O(n) 和空间方面的 n （在最坏的情况下，如果对列表进行排序会好得多）。

它们是整数的事实并没有真正考虑在内，因为将它们相加并没有什么特别的……是吗？

问题

我不明白为什么选择的答案在任何标准上都是“最好的”。O(N*lgN) > O(N)，它会更改列表（或者创建它的副本，这在空间和时间上仍然更昂贵）。我错过了什么吗？

于 2008-08-29T20:12:30.807 回答
0

不过，这取决于数字的大/小/多样化。基数排序可能适用，这将在很大程度上减少 O(N log N) 解决方案的排序时间。

于 2008-08-29T20:33:14.610 回答
0

排序方法和 XOR 方法具有相同的时间复杂度。如果假设两个字符串的按位异或是一个常数时间运算，则异或方法只有 O(n)。这相当于说数组中整数的大小由一个常数限定。在这种情况下，您可以使用基数排序以 O(n) 对数组进行排序。

如果数字没有界限，则按位异或需要时间 O(k)，其中 k 是位串的长度，异或方法需要 O(nk)。现在再次基数排序将在时间 O(nk) 中对数组进行排序。

于 2008-09-01T06:21:50.793 回答
-1

您可以简单地将集合中的元素放入哈希中，直到发现冲突。在红宝石中，这是一个单行。

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

因此，find_dupe([1,2,3,4,5,1])将返回 1。

不过，这实际上是一个常见的“技巧”面试问题。它通常是关于一个重复的连续整数列表。在这种情况下，面试官通常会要求您使用n 整数的高斯和技巧，例如n*(n+1)/2从实际总和中减去。教科书的答案是这样的。

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end
于 2008-08-29T20:27:34.250 回答