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

Question

看完this interesting question我想起了我曾经回答过的一个棘手的面试问题:

You are given an array of n 32-bit unsigned integers where each element (except one) is repeated a multiple of three times. In O(n) time and using as little auxiliary space as possible, find the element of the array that does not appear a multiple of three times.

例如，给定这个数组:

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# 中使用常量空间的方法。我正在使用“除三态位外的异或”的想法。对于每个设置位，“异或”运算都会增加相应的三态值。

最终输出将是其二进制表示在最终值中为 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;
}