在数组中查找唯一整数

Question

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

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

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

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

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

Answer 1

创建一个包含 INT_MAX 个槽的数组 counts，每个元素都初始化为零。
对于输入列表中的每个元素，将 counts[element] 递增 1。（编辑：实际上，你需要做 counts[element] = (counts_element+1)%2，否则你可能会溢出非常大的 N 值的值。做这种模数计数是可以接受的，因为所有重复项出现偶数次)
遍历 counts，直到找到包含“1”的插槽。 Return 该插槽的索引。

第2步是O(N)时间。第 1 步和第 3 步占用大量内存和大量时间，但两者都与输入列表的大小不成正比，所以它们在技术上仍然是 O(1)。

（注意：这假设整数具有最小值和最大值，许多编程语言都是如此。）

Answer 2

跟踪每个元素的计数，并且只跟踪 return 计数为 1 的元素。这可以通过哈希映射来完成。下面的示例在构建计数映射时使用哈希集跟踪结果。仍然是 O(n)，但效率较低，但我认为它稍微更有启发性。

Javascript 与 jsfiddle http://jsfiddle.net/nmckchsa/

function findUnique(arr) {
    var uniq = new Map();
    var result = new Set();
    // iterate through array
    for(var i=0; i<arr.length; i++) {
        var v = arr[i];
        // add value to map that contains counts
        if(uniq.has(v)) {
            uniq.set(v, uniq.get(v) + 1);
            // count is greater than 1 remove from set
            result.delete(v);
        } else {
            uniq.set(v, 1);
            // add a possibly uniq value to the set
            result.add(v);
        }
    }
    // set to array O(n)
    var a = [], x = 0;
    result.forEach(function(v) { a[x++] = v; });
    return a;
}
alert(findUnique([1,2,3,0,1,2,3,1,2,3,5,4,4]));

编辑由于非唯一数字出现偶数次@PeterCordes 建议使用更优雅的设置切换。

这是它的样子。

function findUnique(arr) {
    var result = new Set();
    // iterate through array
    for(var i=0; i<arr.length; i++) {
        var v = arr[i];
        if(result.has(v)) { // even occurances
            result.delete(v);
        } else { // odd occurances
            result.add(v);
        }
    }
    // set to array O(n)
    var a = [], x = 0;
    result.forEach(function(v) { a[x++] = v; });
    return a;
}

JSFiddle http://jsfiddle.net/hepsyqyw/

Answer 3

问题标题说“ 唯一整数”，但问题 body 说可以有多个唯一元素。

如果实际上只有一个non-duplicate：将所有元素异或在一起。重复项全部取消，因为它们成对出现（或 2 的更高倍数），所以结果是唯一的整数。

请参阅 Dante 的回答以了解可以处理两个独特元素的此想法的扩展。不能一概而论。

也许对于 k 个唯一元素，我们可以使用 k 个累加器来跟踪 sum(a[i]**k)。即 a[i]、a[i]² 等。这可能只适用于 Faster algorithm to find unique element between two arrays?，不适用于重复项都在一个数组中的情况。 IDK 如果正方形、立方体等的异或运算对解决问题有任何用处。

Answer 4

有一个标准算法可以使用异或运算符解决此类问题：

时间复杂度 = O(n)

Space 复杂度 = 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 并且 只有只出现一次的数字在我们对数组的所有元素因为

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 的位）并使其余 0.The 结果是一个数字，这将使我们能够区分两个数字（所需的数字） .

因为这个位是1，这意味着他们在这个位置不同，这意味着一个将在这个位置有0，一个将有1.This表示取一个数字并且结果为0而一个没有.

因为设置最右边的位很容易，所以我们将它的结果 xor 设置为

 A = result & ~(result-1)

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

 number_1 = number_1^array[i]

否则

 number_2 = number_2^array[i]

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

所以算法是

1.Take所有元素的异或，称之为异或。

2.Set异或最右位存入B.

3.Do以下：

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 是必需的数字。

Answer 5

这是一个拉斯维加斯算法，给定 k，出现奇数次的元素的确切数量，在预期时间 O(n k) 内报告所有元素（阅读：线性时间当 k 是 O(1)) 和 space O(1) 字时，假设 "give me a uniform random word" 和 "give me the number of 1 bits set in this word (popcount)" 是恒定时间操作。我很确定我不是第一个想出这个算法的人（我什至不确定我是否记得所有的改进），但我已经达到了耐心的极限找到它。

核心技术称为随机限制。本质上，我们所做的是按值随机过滤输入，希望我们只保留一个奇数元素。我们将经典的异或算法应用于过滤后的数组并检查结果；如果成功，那么我们假装将它添加到数组中，使其成为偶数。重复直到找到所有 k 个元素。

过滤过程是这样的。将每个输入词 x 视为长度为 w 的二进制向量（w 是什么无关紧要）。通过 ceil(1 + lg k) 计算大小为 w 的随机二元矩阵 A 和长度为 ceil(1 + lg) 的随机二元向量 b k).我们通过保留 x 这样 Ax = b 来过滤输入，其中左侧是矩阵乘法 mod 2 . 在实现中，A表示为ceil(1 + lg k)向量a1, a2, ...。我们将 Ax 的位计算为 popcount(a1 ^ x), popcount(a2 ^ x), ...。（这很方便，因为我们可以缩短与 b 的比较，这会从运行时间中减少一个因子 lg k。）

分析表明，在给定的传递中，我们设法以恒定的概率挑出一个奇数元素。首先注意，对于一些固定的x，Ax = b的概率是2^{-ceil(1 + lg k)} = Θ(1/k)。鉴于 Ax = b，对于所有 y ≠ x，Ay = b 的概率更小比 2^{-ceil(1 + lg k)}。因此，伴随 x 的预期元素数小于 1/2，因此概率大于 1/2，x 在过滤后的输入。对所有 k 个奇数元素求和（这些事件是不相交的），概率为 Θ(1)。

这是 k = 3 的确定性线性时间算法。令奇数元素为 a, b, c。累加数组的异或，即s = a ^ b ^ c。对于每个位 i，请注意，如果 a[i] == b[i] == c[i]，则 s[i] == a[i] == b[i] == c[i]。再遍历数组，累加s ^ x中设置的最低位的异或。偶数元素再次无贡献。两个奇数元素贡献相同的位并相互抵消。因此，XOR 中设置的最低位恰好是奇数元素之一不同于 s 的位置。我们可以用上面的限制方法找到它，然后用k = 2的方法找到其他的。

Answer 6

假设您有一个输入数组：[2,3,4,2,4] 输出：3

在Ruby中，你可以做一些简单的事情：

[2,3,4,2,4].inject(0) {|xor, v| xor ^ v}

在数组中查找唯一整数

Find a unique integer in an array

arrays

algorithm

integer

unique