在数组中查找不重复三次的元素？

Question

在阅读了这个有趣的问题之后,我想起了曾经有过一次我从未满意地回答的棘手面试问题:

给出一个n个32位无符号整数的数组,其中每个元素(除了一个)重复三次.在O(n)时间内并使用尽可能少的辅助空间,找到不出现三次的数组的元素元素.

举个例子,给定这个数组:

1 1 2 2 2 3 3 3 3 3 3

给定数组时,我们输出1

3 2 1 3 2 1 2 3 1 4 4 4 4

我们输出4.

这可以通过使用哈希表计算每个元素的频率在O(n)时间和O(n)空间中轻松解决,但我强烈怀疑,因为问题语句特别提到数组包含32位无符号整数有一个更好的解决方案(我猜O(1)空间).

有没有人对如何解决这个问题有任何想法？

Answer 1

它可以在O(n)时间和O(1)空间中完成.

以下是如何在C#中使用恒定空间来实现的.我正在使用"xor除了3状态位"之外的想法.对于每个设置位,"xor"操作递增相应的3状态值.

最终输出将是其二进制表示在最终值中为1或2的位置具有1的数字.

void Main() {
    Console.WriteLine (FindNonTriple(new uint[] 
                        {1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3} ));
    // 1

    Console.WriteLine (FindNonTriple(new uint[] 
                        {3, 2, 1, 3, 2, 1, 3, 2, 1, 4, 4, 4, 4} ));
    // 4
}

uint FindNonTriple(uint[] args) {
    byte[] occurred = new byte[32];

    foreach (uint val in args) {
        for (int i = 0; i < 32; i++) {
            occurred[i] = (byte)((occurred[i] + (val >> i & 1)) % 3);
        }
    }

    uint result = 0;
    for (int i = 0; i < 32; i++) {
        if (occurred[i] != 0) result |= 1u << i;
    }
    return result;
}