阅读这个有趣的问题我被提醒一个棘手的面试问题,我曾经有一次我从来没有满意地回答:
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; }更多推荐
在数组中查找不重复三次的元素?
发布评论