arrays - 在数组中查找唯一整数

Question

我正在寻找一种算法来解决以下问题:给定一个大小为 n 的整数数组，其中恰好包含 k (0 < k < n) 个元素一次。每隔一个整数在数组中出现偶数次。输出应该是 k 个唯一数字中的任何一个。 k是一个固定的数字，不是输入的一部分。

一个示例是输入 [1, 2, 2, 4, 4, 2, 2, 3]，其中 1 和 3 都是正确的输出。

最重要的是，该算法应该在 O(n) 时间内运行并且只需要 O(1) 的额外空间。

编辑:对于是否只有一个唯一整数或多个唯一整数存在一些混淆。我为此道歉。正确的问题是有一个任意但固定的数量。我已经更新了上面的原始问题。

“但丁。”对于最多有两个这样的数字的情况给出了很好的答案。 This link还提供了三种解决方案。 “David Eisenstat”评论说对于任何固定的 k 也是可以的。我将不胜感激一个解决方案。

Answer 1

有一个使用异或运算符解决此类问题的标准算法:

时间复杂度 = O(n)

空间复杂度 = O(1)

假设您的输入数组只包含一个元素出现奇数次而其余元素出现偶数次，我们利用以下事实:

任何具有偶数个 0 和 1 的表达式在应用 xor 时总是 = 0。

也就是

0^1^....... = 0 as long as number of 0 is even and number of 1 is even 

并且 0 和 1 可以以任何顺序出现。

因为所有出现偶数次的数字都会有它们对应的位形成偶数个 1 和 0 并且当我们对数组的所有元素进行 xor 时，只有只出现一次的数字会遗漏它的位因为

0(from no's occuring even times)^1(from no occuring once) = 1 

0(from no's occuring even times)^0(from no occuring once) = 0

如您所见，仅保留了出现一次的数字。

这意味着当给定这样一个数组并对所有元素进行异或时，结果是只出现一次的数字。

所以长度为n的数组的算法是:

 result = array[0]^array[1]^.....array[n-1] 

不同的场景

正如 OP 提到的，输入也可以是一个数组，其中两个数字只出现一次，其余出现偶数次。

这是使用与上述相同的逻辑解决的，但差别不大。

算法思路:

如果对所有元素进行异或运算，那么出现偶数次的元素的所有位肯定会得到 0，这意味着:

结果的位 1 仅在两个数字只出现一次的位不同的位位置。

我们将使用上面的想法。

现在我们关注结果为 1 的 xor 位(任何为 1 的位)并将 rest 设为 0。结果是一个数字，可以让我们区分两个数字(所需的数字)。

因为这个位是1，这意味着他们在这个位置上不同，这意味着一个在这个位置上有0，一个在这个位置上有1。这意味着一个数字取AND结果为0，一个没有。

因为设置最右边的位非常容易，所以我们将其设置为异或结果

 A = result & ~(result-1)

现在遍历数组一次，如果array[i]&A为0，将数字存储在变量number_1中作为

 number_1 = number_1^array[i]

否则

 number_2 = number_2^array[i]

因为剩余的数字出现偶数次，所以他们的位会自动消失。

所以算法是

1.对所有元素进行异或，称之为异或。

2.设置异或的最右边位并存入B。

3.执行以下操作:

number_1=0,number_2=0;
for(i = 0 to n-1)
{
 if(array[i] & B)
  number_1 = number_1^array[i];
 else
  number_2 = number_2^array[i];
}

number_1 和 number_2 是必需的数字。