在一百万个数字的集合中，寻找一个唯一的数字的高效算法是什么？

Question

我在面试中被问到了这个问题。在一百万个数字中，除了一个数字以外，其他所有数字都有一个重复的数字。如何找到那个唯一的数字？使用哪种算法可以获得良好的时间和空间复杂度？我想到了使用异或门的方法，但我仍然不知道如何实现。

- user3095838

---

你正在走正确的路，你的问题是什么？向我们展示一下你到目前为止尝试过什么？ - 0xF1

@Angew：“有重复”并不意味着“恰好有两个”，是吗？嗯，我猜从字面上讲是这样的...（但在 Stack Overflow 的意义上不是这样的！ :-)） - Kerrek SB

@KerrekSB 这个问题说的是“有一个重复项”。更不用说为了让XOR起作用，每个重复项必须是偶数个。 - Angew is no longer proud of SO

你了解数字方面的知识吗？有符号/无符号、数据类型，它们是否已经排序，它们是否都是以特定N开头的整数？ - Pandrei

始终牢记额外的问题：找到两个唯一的数字。 - Mikhail

Answer 1

按顺序使用 xor 处理所有数字。

对于以下数字列表：

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

令符号^表示异或操作（或者xor）

则，
1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 2 ^ 1 = 4

- user3164559

---

你应该添加一些解释，你的解决方案是正确的 :) - Pham Trung

System.out.println(1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 3); 输出结果为1。 - Evgeniy Dorofeev

@EvgeniyDorofeev：显然 2 ^ 3 是 1。 - 0xF1

只有每个值出现的次数是偶数，这才能起作用，但我认为在这种情况下“duplicate”意味着“两个”。 - Pham Trung

@MadHatter 但是它应该是2。 - Evgeniy Dorofeev

Answer 2

试试这个

    int[] a = {1, 2, 1, 2, 3};
    Arrays.sort(a);
    for(int i = 0; i < a.length; i++) {
        if (i == 0 && a[i] != a[i + 1] || i == a.length -1 || a[i] != a[i - 1] && a[i] != a[i + 1]) {
            System.out.println(a[i]);
            break;
        }
    }

- Evgeniy Dorofeev

---

那在计算上很昂贵。 - Bathsheba

这需要很长时间...排序算法至少需要O(nlogn)，而你有100万个数据...太多了。 - Tareq Salah

@Angew 对不起，还是个大数字。 - Tareq Salah

@Angew 你是对的，已修复。 - Evgeniy Dorofeev

@TarekSalah 对于今天的计算机来说，一百万并不是很大的数字，可以在毫秒内完成排序。我认为这是更可取的解决方案，因为像X-OR一样，它并不假定重复项是偶数。 - Vikram Bhat

Answer 3

另一个简单的解决方案：可以使用两个位集(bitsets)，一个用于标记数字的存在，另一个用于标记重复。我们遍历数组并标记每个元素的存在和重复。然后我们遍历位集以找到一个被标记为存在但未标记为重复的数字。

int[] numbers = new int[] { 1, 1, 2, 2, 3, 4, 4, 5, 5 };

    BitSet bs1 = new BitSet();
    BitSet bs2 = new BitSet();

    int largestNumber = 0;

    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];
        if (bs1.get(number) == false) {
            // Mark for existence
            bs1.set(number);
        } else {
            // Mark for duplicating
            bs2.set(number);
        }

        if (number > largestNumber) {
            largestNumber = number;
        }
    }

    for (int i = 0; i <= largestNumber; i++) {
        if (bs1.get(i) && !bs2.get(i)) {
            System.out.println("Non duplicating number is:  " + i);
        }
    }

}

- Serdar

---

你增加了内存复杂度... - Jarod42

Answer 4

以下可能解决您的问题：

复杂度： O(N)

// Assuming the duplicate are going by pair
// x ^x == 0 and x ^0 == x
int find_unique(const std::vector<int>& v)
{
    assert(v.size() % 2 == 1);

    int res = 0;
    for (auto value : v) {
        res ^= value;
    }
    return res;
}

或者 复杂度：O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    if (it == v.begin()) { throw std::runtime_error("no unique number"); }
    if (it != v.begin() + 1) { throw std::runtime_error("several unique numbers"); }
    return v[0];
}

复杂度：O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    if (v.size() == 1) { return v[0]; }
    std::sort(v.begin(), v.end());
    if (v[0] != v[1]) { return v[0]; }

    for (int i = 1, size = v.size(); i + 1 < size; ++i) {
        if (v[i] == v[i - 1]) { continue; }
        if (v[i] == v[i + 1]) { ++i; continue; } // we may skip v[i + 1]
        return v[i];
    }
    return v.back();
}

- Jarod42

Answer 5

对于大量的输入项（与仅有几个数字的示例相反），将输入放入某些数据结构中需要相当长的时间。我考虑利用这个必要的时间作为计算过程的一部分，将其放入一个映射中。映射的值只有一个单一的数字。我假设数据是正确的，所以我省略了检查，但如果有多个数字仅出现一次，它将返回第一个数字。

应该有进一步优化的空间，例如通过按值访问映射并查找具有1的映射。我认为这可以很容易地使用Boost.Bimap完成。

int getSingleNumber(){

map<int, int> numbers;

for (all input items)
    {
    numbers[currentInputItem]++;
    }

for( map<int,int>::iterator ii=numbers.begin(); ii!=numbers.end(); ++ii)
{
    if ( (*ii).second == 1 ) return (*ii).first;
}
}

- Draugr

Answer 6

我相信如果我们将快速排序（搜索）技术和异或运算结合起来，我们可以得到最快的代码。虽然我正在尝试，但同时请纠正我这个想法是否错误。

顺便说一下，这有很多用例。虽然问题与语言无关，需要清晰的算法，但我提到了一些读者可能会发现有用的用例。

0可能是重复的...或负数...

System.out.println(33 ^ 33 ^ 7 ^ 0 ^ 0 ^ 5 ^ 7 ^ 5);返回0（这里是一个重复项）

重复项可能超过2个：

System.out.println(1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 3);返回1，而不是2...

等等，这个问题可能比我们最初想象的要复杂。

- Siva Tumma