找出仅出现一次的三个数字

Question

在长度为n（其中n=2k+3）的序列中，有k个数字出现了两次，而另外三个数字仅出现一次。

问题是：如何找到这三个仅出现一次的数字？

例如，在序列1 1 2 6 3 6 5 7 7中，三个独特的数字是2、3和5。

注意： 3≤n<1e6并且数字范围在1至2e9之间。 内存限制：1000KB，这意味着我们不能存储整个序列。

我尝试过的方法（超出了内存限制）： 我初始化了一个树，在读入一个数时，我尝试从树中删除它，如果删除返回false（未找到），我就将其添加到树中。最后，树中有三个数字。这个方法可以工作，但超出了内存限制。

我知道如何使用位运算找到一个或两个这样的数字。因此，我想知道是否可以使用相同的方法（或类似的方法）找到三个数字？

找到一个/两个只出现一次的数字的方法： 如果一个数字仅出现一次，则可以对序列应用XOR来查找它。

如果有两个数字，我们可以先对序列应用XOR，然后通过结果中的一个位将序列分成两个部分，并再次对这两个部分进行XOR，就能找到答案。

- shilk

---

深奥的问题加上没有用处，是否就成了作业？ - Robert Harvey

@Robert Harvey - 可能是一个Project Euler问题 - David Basarab

将此问题标记为“作业”、“面试问题”、“编程竞赛”或类似的内容可以帮助回答者更恰当地表达他们的答案，并在过程中更加诚实。 - Jason Hall

@shilk：内存限制并不一定意味着您只能查看列表一次。例如，您可以完全使用缓冲区。 - Matthieu M.

“Esoteric question + no useful purpose = homework?”这个问题即使不是作业，也在理论驱动的纯粹思考层面上。 - Evan Plaice

Answer 1

对于一个更一般的问题（不带那些愚蠢的限制）：

您可以在O(n)时间和O(1)空间内完成此操作，而不需要假设任何边界，或者迭代所有位，并且只使用O(1)时间比特操作技巧，例如XOR技巧，该技巧适用于2个缺失的数字。

以下是（伪）代码，可用于查找其中一个数字：

// 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，其余位均为零。将此数字称为diff(x)。

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

注意，d不能为零。

现在找到d的最低位。可以使用该位位置来分类出a、b、c中的一个数字，因为不可能所有的数字都在该位置具有相同的位：如果是这样，那么这三个数字的XOR值s的该位必须相同，但我们确保我们选择的s的该位与a、b、c中的至少一个相应位不同。

所以我们再次进行XOR，区分这个位，并检查哪个结果数字在数组中只出现一次。一旦我们找到一个数字，就知道如何处理两个数字。

要找到diff，只需使用bithack：x & ~(x-1)，这是一种标准的位操作技巧，可以视为O（1）（而不是O（位数））。

- Aryabhatta

Answer 2

这是一个经典问题，我几周前刚被问到。为了解决它，你需要确定可能出现的不同数字数量，并分配相应数量的位。

例如，如果列表中的数字必须介于1-20之间，则需要分配20位——每个数字一位，并将每个位初始化为0。

然后遍历列表。每次看到一个数字，就翻转相应的位。

例如：对于你的示例列表2 6 3 6 5 7 7，我们可以分配7个位（代表1 2 3 4 5 6 7）。然后在遍历列表时，我们会执行以下操作：

- 翻转第2位 - 翻转第6位 - 翻转第3位 - 翻转第6位 - 等等

然后，在完成遍历列表后，您可以阅读位以查找三个唯一的数字。它们都将由“1”位表示，其他数字将由0表示。

您需要两次读取列表，这需要2n时间，即O(n)。

编辑：可能不会给出范围。一种解决方案是首先读取列表以确定其范围，然后仍然是O(n)。

但是，可能会出现一个问题，即列表可能非常小，但是某些数字非常大，从而使范围太大。例如：

1, 99999999999999999, 1, 99999999999999999, 2, 3, 4

解决这个问题需要大量的内存，因为列表中有很多数字，尽管数字很少，但范围很大，我们根据范围分配位。

可以使用哈希表进行调整以提供新的解决方案（虽然我不确定是否允许这样做，因为问题的规定是“仅限位操作”）：

1. 让L表示原始列表，C表示其副本。 2. 从C中删除所有重复项（有许多有效的方法可实现此目的）。 3. 创建哈希表H，并为C中的每个元素插入一个键/值对到H中。其中，number是C中的当前元素，pos是它在C中的位置。因此，给定出现在L中的数字，我们现在可以使用H找到该数字在C中的位置。 4. 分配与C大小相等的位数，并将这些位初始化为0。 5. 遍历L。每次遇到一个数字时，从H获取其值，并翻转我们的位列表中的那个位。 6. 遍历位列表 - 对于每个'1'位，从C中获取该位置处的数字，即其中之一的唯一数字。

- Cam

---

原始问题提到了有界数吗？ - Akusete

谢谢您的回复。我之前想过这种方法。但是数字范围是1-2e9，n是3-1e6。所以这种方法行不通。 - shilk

@shilk：我已经相应地编辑了我的答案。你可以使用哈希表来解决这个问题。 - Cam

@Cam：是的，我对边界相当确定。由于我们无法存储整个列表，因此我们只能读取并操作一个。 - shilk

如果您可以将所有值放入哈希表中，则可以直接使用它来解决问题，无需添加位集。 - Dave L.

Answer 3

您可以以类似的方式处理一个或两个不同值的简单情况。

我们需要为每个数字的位（例如32位）准备两个整数。对于每个数字，如果该位为零，则使用第一个整数进行异或运算。否则，使用第二个整数进行异或运算。

此外，请记录在每个位置上找到1或0的次数（我们只需要检查这是偶数还是奇数，因此请保持布尔值）。

遍历后，我们的整数对将是以下之一：这里的第一个数字表示偶数计数，第二个数字表示奇数计数。

0, a^b^c
a^b, c
a^c, b
b^c, a

对于每一对数，检查偶数计数整数。如果它是零，则我们知道另一个整数是a^b^c，因为我们的结果中没有两个相等的值。否则，我们已经发现了奇数计数整数的值。

public static int[] find3(int[] list) {
    int[][] xors = new int[32][2];
    boolean[] counts = new boolean[32];
    for (int curr : list) {
        for (int i = 0; i < 32; i++) {
            xors[i][(curr & (1 << i)) >> i] ^= curr;
            counts[i] ^= ((curr & (1 << i)) == (1 << i));
        }
    }

    // this really shouldn't take so many lines
    int[] ret = new int[3];
    int found = 0;
    for (int i = 0; i < 32; i++) {
        int oddCount = xors[i][counts[i] ? 1 : 0];
        int evenCount = xors[i][counts[i] ? 0 : 1];
        if (evenCount != 0) { // avoid the 0, a^b^c case.
            if (found == 0) {
                ret[0] = oddCount;// a
                ret[2] = evenCount;// b^c for now
                found++;
            } else if (found == 1 && ret[0] != oddCount) {
                ret[1] = oddCount;// b
                ret[2] ^= oddCount;// (b^c)^b == c
                break;
            }
        }
    }
    return ret;
}

- Nabb

---

@shilk。我同意。对于所述范围，这是一个很好的解决方案。 - Aryabhatta

Answer 4

如果概率解决方案足够，您可以使用布隆过滤器。

创建两个布隆过滤器。第一个（A）包含至少找到一次的数字，第二个（B）包含找到两次的数字。

伪代码：

A = empty
B = empty

foreach x in the list
  if x in A
    add x to B
  else
    add x to A

foreach x in the list
  if x in A
    if !(x in B)
      print x

如果您使用完整的1000KB，则错误的概率将非常低。

- Peter Alexander

---

你如何遍历列表两次，因为我们没有足够的内存来存储整个列表？我认为在这种情况下布隆过滤器不起作用。 - shilk

@shilk：布隆过滤器是一种高度紧凑的位数组，所以它非常节省空间。通过将多个哈希函数的索引hashcode % array.length处的位设置为1，你可以向布隆过滤器中“添加”项目，并且你可以以类似的方式测试是否存在于集合中。这是一个完全足够、概率性的解决方案来回答你的问题。 - Juliet

@Juliet，他说的第二次遍历是正确的。你不能使用布隆过滤器重新遍历元素，同时我们也不能存储这些元素 :-/ -- 我错过了那一部分。 - Peter Alexander

Answer 5

随着增加更多的独特值，问题变得越来越困难，主要是因为可以选择A、B、C，使得A xor B xor C = 0。如果子集包含了所有唯一值，或者省略了Xor到0的值，那么检测这些值是否具有相同的校验和就会变得越来越困难。

您可以在常量空间和O(n*k)时间内处理3个值，其中k是最大整数中的位数。（因此，在32位整数的典型情况下，时间复杂度为O(n)。）

随着唯一值的数量增加且要求保持恒定的空间，时间上界是否变为非线性将是有趣的研究方向。

//Special check for 0, because otherwise we don't know A xor B xor C != A xor B
if items unique-contains 0 then
    return 0 ++ SubProblem2Unique(items - 0)
//Compute A xor B xor C
val x = fold xor items
//Try to find a split which separates A and B from C.
for i in 0..WORD_SIZE
    //see if the checksum splits
    val x1 = fold xor [e in items where e & (1<<i) == 0]
    val x2 = x xor x1
    if x1 == x or x2 == x then continue //ith bit was the same for A and B and C
    //C is either x1 or x2
    val C = if items unique-contains x1 then x1 else x2
    return C ++ SubProblem2Unique(items - C)

throw InvalidInput

- Craig Gidney

Answer 6

为什么不使用哈希集？ - 如果数字已经存在，则从哈希集中删除 - 如果数字不存在，则放入哈希集中 最终哈希集仅包含唯一数字。 时间：O（n） 内存：o（k），其中k是不同元素的数量。

使用哈希集方法，该解决方案可扩展，并可用于确定任何给定序列中的任意数量的唯一元素。

- Amit

---

因为你无法将五十万个32位值装入1000 KB的哈希集合中。 - Dave L.