算法找到数组中的两个重复的数字，不排序 [英] Algorithm to find two repeated numbers in an array, without sorting

问题描述

有大小为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。 [你不应该使用排序]

P.S. [You should not use sorting]

推荐答案

有一个 O（n）的解决方案如果您知道输入的可能域。例如，如果你输入数组包含数字0到100之间，考虑以下code。

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.

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