在数组中查找不重复三倍的元素? [英] 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) 时间内，使用尽可能少的辅助空间，找到数组中不出现 3 次倍数的元素.

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# 中使用常量空间的方法.我正在使用xor，除了三态位"的想法.对于每个设置位，异或"操作都会增加相应的三态值.

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 的位置为 1 的数字.

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屋！