找到三个号码只出现一次

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(未找到),我将它添加到树中.最后,树有三个数字.它工作,但内存限制超过.

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

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

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

如果只有一个数字出现一次,我们可以对序列应用XOR来找到它.

如果有两个,我们可以先对序列应用XOR,然后将序列分成2个部分,结果为1,然后再将XOR应用于2个部分,我们将找到答案.

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中的一个,因为不是所有的a,b,c都可以在那个位置有相同的位:如果它们这样做,那么s的那个位是那个位的XOR三个必须是相同的,但我们确保我们选择s的这一位与a,b,c中的至少一个相应位不同.

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

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

Answer 2

这是一个经典的问题 - 几周前我才真正问过它.要解决这个问题,您需要获取可能出现的可能不同数字的数量,并分配那么多位.

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

然后你遍历列表.每次看到一个数字,都要翻转相应的位.

例如:使用您的示例列表2 6 3 6 5 7 7,我们可以分配7位(1 2 3 4 5 6 7).然后,当我们遍历列表时,我们将执行以下操作:

• 翻转第二位
• 翻转第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中,插入一个键/值对< number,pos>成H,其中number在当前的元件C,并且pos是在其位置C.因此,给定一个出现的数字L,我们现在可以H用来找到该数字的位置C.
4. 分配等于大小的C位数,并将这些位初始化为0.
5. 遍历L.每次我们运行一个数字,从中获取其值H,并在我们的位列表中翻转该位.
6. 遍历位列表 - 对于每个'1'位,获取该C位置的数字 - 这是唯一的数字之一.

Answer 3

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

对于数字的每个位,我们需要两个整数(例如32位).对于每个数字,如果该位为零,则对其进行XOR第一个整数.如果不是,则用它对第二个整数进行异或.

另外,记住你在每个位置找到1或0的次数(我们只需要检查它是偶数还是奇数,所以保持一个布尔值).

迭代后,我们的整数对将是以下之一.这里的第一个数字表示偶数,第二个数字表示奇数.

0, a^b^c
a^b, c
a^c, b
b^c, 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;
}

Answer 4

如果概率解决方案足够,那么您可以使用布隆过滤器.

创建两个Bloom过滤器.第一个(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,那么错误的概率将是非常低的.