找到三个数字只出现过一次 [英] Find three numbers appeared only once

问题描述

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

In a sequence of length n, where n=2k+3, that is there are k unique numbers appeared twice and three numbers appeared only once.

现在的问题是：如何找到只出现过一次的三个独特的数字

例如，在序列1 1 2 3 6 6 5 7 7三个唯一号码2 3 5

for example, in sequence 1 1 2 6 3 6 5 7 7 the three unique numbers are 2 3 5.

请注意： 3'; =正＆其中; 1e6个和数目的范围从1至2E9

Note: 3<=n<1e6 and the number will range from 1 to 2e9

内存限制：1000KB，这意味着我们不能存储整个序列

Memory limits: 1000KB , this implies that we can't store the whole sequence.

方法我都试过（内存限制超过）：

我初始化一棵树，并在一个数字阅读时，我尝试从树上取下，如果  取出假（未找到），我把它添加到树。最后，该树有三个数字。它的工作原理，但内存超限。

I initialize a tree, and when read in one number I try to remove it from the tree, if the remove returns false(not found), I add it to the tree. Finally, the tree has the three numbers. It works, but is Memory limit exceed.

我知道如何找到使用位操作一个或两个这样的号码。所以我想如果

I know how to find one or two such number(s) using bit manipulation. So I wonder if

我们可以发现三个使用相同的方法（或类似方法的一些）？

we can find three using the same method(or some method similar)?

方法查找一/二号码只出现过一次：

如果有一个数字只出现过一次，我们可以应用XOR到序列找到它。

If there is one number appeared only once, we can apply XOR to the sequence to find it.

如果有两个，我们可以首先应用异或向序列，然后分离序列划分成2 份结果是是1，以及再次应用异或到2份，和我们将找到答案。的一个位

If there are two, we can first apply XOR to the sequence, then separate the sequence into 2 parts by one bit of the result that is 1, and again apply XOR to the 2 parts, and we will find the answer.

推荐答案

可以以类似的方式执行此操作的一个和两个不同的值的简单的情况

You can do this in a similar way to the simpler cases of one and two different values.

我们需要两个整数的数字（例如32位）的每一位。对于每一个数字，如果该位为0，异或与它的第一个整数。如果不是，XOR与它的第二整数

We need two integers for each bit of the numbers (e.g. 32 bits). For each number, if that bit is zero, XOR the first integer with it. If it isn't, XOR the second integer with it.

另外，请你有多少次发现1或0的每个位置的数（我们只需要检查，如果这是奇数还是偶数，所以保持一个布尔值）。

Also, keep count of how many times you find a 1 or 0 in each position (we only need to check if this is even or odd, so keep a boolean).

通过迭代后，我们对整数将是下列情况之一。这里的第一个号码重新presents甚至数，第二个奇怪的。

After iterating through, our pairs of integers will be one of the following. The first number here represents an even count, the second an odd.

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

对于每一对，检查即便算上整数。如果它是零，那么我们知道其他整数是一个^ B ^ C，因为没有两个我们的结果将是相等的。否则，我们发现，在奇计整数值。

For each pair, check the even count integer. If it is zero, then we know the other integer is a^b^c, since no two of our results will be equal. Otherwise, we've found a value at the odd count integer.

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;
}

这篇关于找到三个数字只出现过一次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！