发现在不重复三次的倍数的阵列的元素？ [英] Finding an element in an array that isn't repeated a multiple of three times?

问题描述

看完<一href="http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-time">this有趣的问题我想起了一个棘手的面试问题我曾经，我从来没有满意的回答：

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.

作为一个例子，考虑到本数组：

As an example, given this array:

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＃中恒的空间去做。我使用的想法，除了异或具有三态位。对于每一个设置位的异或操作的增量对应的三态值。

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.

的最终输出将是其二进制重新presentation具有1秒在于要么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屋！