在数组中查找不重复三倍的元素？

Question

阅读后这个有趣的问题让我想起了我曾经遇到过的一个棘手的面试问题，但我从未给出令人满意的答案：

给定一个由 n 个 32 位无符号整数组成的数组，其中每个元素（除了一个）都重复三倍。在 O(n) 时间内，使用尽可能少的辅助空间，找到数组中未出现 3 次倍数的元素。

举个例子，给定这个数组：

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

Answer 2

在恒定空间中执行此操作的明显解决方案是使用就地算法对其进行排序，然后在数组上扫描一次。

遗憾的是，这通常需要 O(n log n) 时间和 O(1) 空间。

但由于条目的密钥长度有限（32 位），您可以使用基数排序作为排序算法（存在就地基数排序，它们不稳定，但这并不重要）。在那里你有 O(n) 时间和 O(1) 空间。

编辑：顺便说一句，您可以使用这种方法来查找所有出现次数不是 3 倍数的数字，以防万一您允许多个数字可以具有此属性。

Answer 3

您正在寻找重复次数非零 (mod 3) 的项目。我想我会递归地做到这一点：

1. 将数组分成两半，
2. 找到每一半中代表计数非零（mod 3）的项目，
3. 合并两半，保留不相等键的计数，并添加相等键的计数，
4. 删除任何count = 0 (mod 3)
5. 将其返回为输入当前部分的值集。

甚至不需要尝试优化基本算法之外的东西（例如，不用担心每次计数只存储两位），这似乎做得很好。我已经添加了代码来生成相当大的测试用例（例如，1500 多个项目）并打印出它正在创建的地图的大小。在任何给定时间，它创建的地图中似乎最多有大约 50 个项目（即，它一次只使用两个地图，我见过的最大的项目约为 25 个）。从技术上讲，就目前情况而言，我相信目前的时间复杂度类似于 O(N log N)，但如果您切换到基于哈希的容器，我相信您会期望 O(N)。

#include <map>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <time.h>

class zero_mod { 
    unsigned base;
public:
    zero_mod(unsigned b) : base(b) {}

    bool operator()(std::pair<int, int> const &v) { 
        return v.second % base == 0; 
    }
};

// merge two maps together -- all keys from both maps, and the sums 
// of equal values.
// Then remove any items with a value congruent to 0 (mod 3)
//
std::map<int, int> 
merge(std::map<int, int> const &left, std::map<int, int> const &right) { 
    std::map<int, int>::const_iterator p, pos;
    std::map<int, int> temp, ret;

    std::copy(left.begin(), left.end(), std::inserter(temp, temp.end()));
    for (p=right.begin(); p!=right.end(); ++p) 
        temp[p->first] += p->second;
    std::remove_copy_if(temp.begin(), temp.end(), 
                        std::inserter(ret, ret.end()), 
                        zero_mod(3));
    return ret;
}   

// Recursively find items with counts != 0 (mod 3):    
std::map<int, int> 
do_count(std::vector<int> const &input, size_t left, size_t right) { 
    std::map<int, int> left_counts, right_counts, temp, ret;

    if (right - left <= 2) {
        for (size_t i=left; i!=right; ++i) 
            ++ret[input[i]];
        return ret;
    }
    size_t middle = left + (right-left)/2;
    left_counts = do_count(input, left, middle);
    right_counts = do_count(input, middle, right);
    ret = merge(left_counts, right_counts);

    // show the size of the map to get an idea of how much storage we're using.
    std::cerr << "Size: " << ret.size() << "\t";
    return ret;
}

std::map<int, int> count(std::vector<int> const &input) { 
    return do_count(input, 0, input.size());
}

namespace std { 
    ostream &operator<<(ostream &os, pair<int, int> const &p) { 
        return os << p.first;
    }
}

int main() {
    srand(time(NULL));
    std::vector<int> test;

    // generate a bunch of data by inserting packets of 3 items    
    for (int i=0; i<100; i++) {
        int packets = std::rand() % 10;
        int value = rand() % 50;
        for (int i=0; i<packets * 3; i++) 
            test.push_back(value);
    }

    // then remove one item, so that value will not occur a multiple of 3 times
    size_t pos = rand() % test.size();
    std::cerr << "Removing: " << test[pos] << " at position: " << pos << "\n";

    test.erase(test.begin()+pos);

    std::cerr << "Overall size: " << test.size() << "\n";

    std::random_shuffle(test.begin(), test.end());

    // Note that we use a map of results, so this will work if multiple values
    // occur the wrong number of times.    
    std::map<int, int> results = count(test);

    // show the results. Should match the value shown as removed above:
    std::copy(results.begin(), results.end(), 
        std::ostream_iterator<std::pair<int, int> >(std::cout, "\n"));
    return 0;
}

Answer 4

计算每个位的总数（0-31，假设 int 是 32 位）并将每个位的计数存储在数组中。完成后，迭代生成的位计数数组，并检查哪个位位置出现的次数不是模 3 次，并根据这些位构造最终的数字。完整的代码如下（也适用于负数）：

void get_num_bits(int n, vector<int>& vbits)
{
    int k = 0;
    vbits.resize(32);
    std::fill(vbits.begin(), vbits.end(), 0);

    uint32_t val = (uint32_t) n;
    printf("%u\n", val);

    if (n < 0)
    {
        while(val)
        {
            if ((1 & val) == 1)
                vbits[k] = 1;
            ++k;
            val = val >> 1;
        }
        return;
    }

    while(n)
    {
        if ((1 & n) == 1)
            vbits[k] = 1;
        ++k;
        n = n >> 1;
    }
}

void sum_bit_counts(vector<int>& all_bits, vector<int>& num_bits)
{
    for (int i = 0; i < num_bits.size(); ++i)
    {
        all_bits[i] += num_bits[i];
    }
}

int single_number(vector<int>& nums) 
{
    vector<int> all_bits(32);

    for (int i = 0; i < nums.size(); ++i)
    {
        vector<int> bits(32);   
        get_num_bits(nums[i], bits);
        sum_bit_counts(all_bits, bits);
    }

    int rv = 0;
    for (int i = 0; i < all_bits.size(); ++i)
    {
        if (all_bits[i] && (all_bits[i] % 3 != 0))
        {
            rv = rv | (1 << i);
        }
    }
    
    return rv;
}