在数组中查找两个重复数字的算法，无需排序

问题描述

有一个大小为 n 的数组(数字在 0 到 n - 3 之间)，并且只重复了 2 个数字.元素在数组中随机放置.

There is an array of size n (numbers are between 0 and n - 3) and only 2 numbers are repeated. Elements are placed randomly in the array.

例如在{2, 3, 6, 1, 5, 4, 0, 3, 5}中n=9，重复数为3和5.

E.g. in {2, 3, 6, 1, 5, 4, 0, 3, 5} n=9, and repeated numbers are 3 and 5.

找到重复数字的最佳方法是什么?

What is the best way to find the repeated numbers?

附言[你不应该使用排序]

P.S. [You should not use sorting]

推荐答案

如果您知道输入的可能域是什么，则有一个 O(n) 解决方案.例如，如果您的输入数组包含 0 到 100 之间的数字，请考虑以下代码.

There is a O(n) solution if you know what the possible domain of input is. For example if your input array contains numbers between 0 to 100, consider the following code.

bool flags[100];
for(int i = 0; i < 100; i++)
    flags[i] = false;

for(int i = 0; i < input_size; i++)
    if(flags[input_array[i]])
         return input_array[i];
    else
        flags[input_array[i]] = true;

当然有额外的内存，但这是最快的.

Of course there is the additional memory but this is the fastest.

这篇关于在数组中查找两个重复数字的算法，无需排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！