在数组中查找不重复三次的元素？ [英] Finding an element in an array that isn't repeated a multiple of three times?

问题描述

阅读这个有趣的问题我被提醒一个棘手的面试问题，我曾经有一次我从来没有满意地回答：

After reading this interesting question I was reminded of a tricky interview question I had once that I never satisfactorily answered:

你给出了n个32位无符号整数的数组，其中每个元素（除了一个）重复三次的倍数。在O（n）时间，尽可能少的辅助空间，找到不出现三次的数组的元素。

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 1 2 2 2 3 3 3 3 3 3

我们输出1，而给定数组

We would output 1, while given the array

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

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

我们将输出4。

这可以通过使用哈希表来计算每个元素的频率来在O（n）时间和O（n）空间中很容易地解决，尽管我强烈怀疑因为问题陈述具体提到数组包含32位无符号整数，有一个更好的解决方案（我猜猜O（1）空间）。

This can easily be solved in O(n) time and O(n) space by using a hash table to count the frequencies of each element, though I strongly suspect that because the problem statement specifically mentioned that the array contains 32-bit unsigned integers that there is a much better solution (I'm guessing O(1) space).

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

Does anyone have any ideas on how to solve this?

推荐答案

可以在O（n）时间和O（1）空间中完成

It can be done in O(n) time and O(1) space.

这是你怎么样可以用C＃中的恒定空间来做到这一点。我使用xor除了3状态位的想法。对于每个设置位，xor操作将增加相应的3态值。

Here is how you can do it with constant space in C#. I'm using the idea of "xor except with 3-state bits". For every set bit, the "xor" operation increments the corresponding 3-state value.

最终输出将是二进制表示在有两个1或2在最终值。

The final output will be the number whose binary representation has 1s in places that are either 1 or 2 in the final value.

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

这篇关于在数组中查找不重复三次的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！