algorithm - 找出三个数字只出现一次

Question

在一个长度为n的序列中，其中n=2k+3，即有k个唯一的数出现了两次三个数字只出现一次。

问题是:如何找到只出现一次的三个唯一数字？

例如，在序列 1 1 2 6 3 6 5 7 7 中，三个唯一数字是 2 3 5。

注意:3<=n<1e6，数字范围从 1 到 2e9

内存限制:1000KB，这意味着我们无法存储整个序列。

我试过的方法(超过内存限制):

我初始化一棵树，当读入一个数字时，我尝试将它从树中删除，如果 remove 返回 false(未找到)，我将其添加到树中。最后，树有三个数字。它有效，但超出了内存限制。

我知道如何使用位操作找到一两个这样的数字。所以我想知道是否

我们可以使用相同的方法(或类似的方法)找到三个吗？

查找一个/两个数字只出现一次的方法:

如果有一个数字只出现过一次，我们可以对序列进行异或来找到它。

如果有两个，我们可以先对序列进行异或，然后将序列分成2结果为1的一位，再对两部分进行异或运算，就可以找到答案了。

Answer 1

对于此问题的更一般版本(没有那些愚蠢的限制):

您可以在 O(n) 时间和 O(1) 空间内完成此操作， 无需假设任何边界，或者迭代所有位，和 仅使用 O(1) 时间位操作技巧，例如对 2 个缺失数字有效的 XOR 技巧。

这里是(伪)代码，只查找其中一个数字:

// Given an array arr with 2k+3 numbers, k of which are repeated twice
// and the remaining three are distinct: a,b,c.
// returns one of a,b,c.
int FindUnique(int []arr) {

    int s = 0; // This will ultimately hold a ^ b ^ c (bitwise XOR)

    for (int i = 0; i < arr.Length; i++) {
        s ^= arr[i];
    }

    int d = 0; // this holds diff(a,s) ^ diff(b,s) ^ diff(c,s)

    for (int i = 0; i < arr.Length; i++) {
        d ^= diff(arr[i],s);
    }

    int e = lowestBit(d); // This gives the position where one of a,b,c differs 
                          // from the others.

    int bucket1 = 0;
    int bucket2 = 0;

    for (int i = 0; i < arr.Length; i++) {
        if (arr[i] & e) {
            bucket1 ^= arr[i];
        } else {
            bucket2 ^= arr[i];
        }
    }

    int count1 = 0;
    int count2 = 0;

    for (int i = 0; i < arr.Length; i++) {
        if (arr[i] == bucket1) {
            count1++;
        }

        if (arr[i] == bucket2) {
            count2++;
        }
    }

    if (count1 == 1) return bucket1;

    return bucket2;
}

// return a number with the lowest bit of x ^ s set to 1 and rest 0.
// i.e. the lowest bit position where x and s differ.
int diff(int x, int s) {
    return lowestBit(x ^ s);
}

// Returns a number with only the lowest bit of y set.
int lowestBit(int y) {
    return y & ~(y-1);
}

思路如下:

假设出现一次的数字是 a,b,c。

现在通过数组运行 XOR 得到 s = a XOR b XOR c。

由于数字是不同的，请注意 s 不能是 a 或 b 或 c(因为其他两个将相等)，因此至少有一位(不一定在同一位置)，其中每个a,b,c 与 s 不同。

在两个数字的情况下，我们可以看到 s 是非零的，并选择一个区分 a 和 b 的位并使用它。

当我们有三个数字时，我们会遇到困难，但我们仍然可以找到一点来区分其中一个数字。

对于每个数字 x，找到与 s 不同的最低位。考虑二进制数，其中只有该位设置为 1，其余位为 0。称这个数字为 diff(x)。

现在，如果我们为每个数字计算 diff(x) 并将它们异或在一起，我们得到 d = diff(a) XOR diff(b) XOR diff(c)。

注意 d 不能为零。

现在找到d的最低集合位。该位位置可用于存储 a、b、c 中的一个，因为并非所有 a、b、c 都可以在该位置具有相同的位:如果有，则 s 的那位是这些位的异或三个必须相同，但我们确保我们选择的 s 的那一位与 a、b、c 中的至少一个对应位不同。

所以我们再次异或，对这个位进行微分，并检查两个结果数字中的哪一个在数组中恰好出现一次。一旦找到一个数字，我们就知道如何处理两个数字。

要找到差异，只需使用 bithack:x & ~(x-1)，这是一个标准的 bit-hack，可以被认为是 O(1)(而不是 O(数量位))。