algorithm在数组中查找两个重复的数字，而不进行sorting

有一个大小为n的数组（数字在0和n – 3之间），只有2个数字重复。 元素随机放置在数组中。

例如在{2,3,6,1,5,4,0,3,5}中n = 9，重复的数字是3和5。

find重复数字的最佳方法是什么？

PS [你不应该使用sorting]

Answer 1

如果您知道可能的input域是什么，那么有一个O（n）解决scheme 。 例如，如果您的input数组包含0到100之间的数字，请考虑以下代码。

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; 

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

Answer 2

好吧，似乎我只是不能给它rest:)

最简单的解决scheme

 int A[N] = {...}; int signed_1(n) { return n%2<1 ? +n : -n; } // 0,-1,+2,-3,+4,-5,+6,-7,... int signed_2(n) { return n%4<2 ? +n : -n; } // 0,+1,-2,-3,+4,+5,-6,-7,... long S1 = 0; // or int64, or long long, or some user-defined class long S2 = 0; // so that it has enough bits to contain sum without overflow for (int i=0; i<N-2; ++i) { S1 += signed_1(A[i]) - signed_1(i); S2 += signed_2(A[i]) - signed_2(i); } for (int i=N-2; i<N; ++i) { S1 += signed_1(A[i]); S2 += signed_2(A[i]); } S1 = abs(S1); S2 = abs(S2); assert(S1 != S2); // this algorithm fails in this case p = (S1+S2)/2; q = abs(S1-S2)/2; 

一个和（S1或S2）包含p和q同一符号，另一个和 – 相反的符号，所有其他成员都被淘汰。
S1和S2必须有足够的位来容纳和，algorithm不会因abs（）而溢出。

如果abs（S1）== abs（S2）那么algorithm失败，虽然这个值仍然是p和q之间的差（即abs（pq）== abs（S1））。

先前的解决

我怀疑有人会在这个领域遇到这样的问题;）
我猜，我知道老师的期望：

让我们取数组{0,1,2，…，n-2，n-1}，
给定的一个可以通过用未知的p和q来代替后两个元素n-2和n-1（更less的顺序）

因此，元素的总和将是（n-1）n / 2 + p + q – （n-2） – （n-1）
（n-1）n（2n-1）/ 6 + p ^ 2 + q ^ 2 – （n-2）^ 2 – （n-1）^ 2

简单的math依然是：

  (1) p+q = S1 (2) p^2+q^2 = S2 

当然，你不会像math课所教导的那样求解方程。

首先，计算一切模2 ^ 32，即允许溢出。
然后根据expression式（2）检查{p，q}对{0，S1}，{1，S1-1} …来找出候选者（由于模和平方可能有2个以上）
最后检查find的候选人是否真的在arrays中出现两次。

Answer 3

你知道你的数组包含从0到n-3的每个数字和两个重复的（p＆q）。 为了简单起见，我们暂且忽略0情况。

您可以计算数组的总和和乘积，从而导致：

 1 + 2 + ... + n-3 + p + q = p + q + (n-3)(n-2)/2 

所以如果从整个数组的总和中减去（n-3）（n-2）/ 2，就可以得到

 sum(Array) - (n-3)(n-2)/2 = x = p + q 

现在为产品做同样的事情：

 1 * 2 * ... * n - 3 * p * q = (n - 3)! * p * q prod(Array) / (n - 3)! = y = p * q 

你现在得到这些条款：

 x = p + q y = p * q => y(p + q) = x(p * q) 

如果你转换这个术语，你应该能够计算p和q

Answer 4

你可能可以利用sum（array）=（n-2）*（n-3）/ 2 +两个缺失数字的事实。

编辑：正如其他人已经注意到，加上平方和，你可以使用这个，我只是有点慢慢计算出来。

Answer 5

将每个元素插入一个集合/哈希表，首先检查它是否已经在它。

Answer 6

在这个主题上检查这个旧的，但很好的论文：

• 查找重复元素 （PDF）

Answer 7

一些问题的答案： 确定数组是否包含n … n + m的algorithm？ 包含作为一个子问题的解决scheme，你可以采取你的目的。

例如，以下是我的答案中的一个相关部分：

 bool has_duplicates(int* a, int m, int n) { /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int') Whether a[] array has duplicates. precondition: all values are in [n, n+m) range. feature: It marks visited items using a sign bit. */ assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN for (int *p = a; p != &a[m]; ++p) { *p -= (n - 1); // [n, n+m) -> [1, m+1) assert(*p > 0); } // determine: are there duplicates bool has_dups = false; for (int i = 0; i < m; ++i) { const int j = abs(a[i]) - 1; assert(j >= 0); assert(j < m); if (a[j] > 0) a[j] *= -1; // mark else { // already seen has_dups = true; break; } } // restore the array for (int *p = a; p != &a[m]; ++p) { if (*p < 0) *p *= -1; // unmark // [1, m+1) -> [n, n+m) *p += (n - 1); } return has_dups; } 

程序保持数组不变（数组应该是可写的，但是它的值在退出时被恢复）。

它适用于高达INT_MAX数组大小（在64位系统上是9223372036854775807 ）。

Answer 8

 假设数组是

 a [0]，a [1]，a [2] ..... a [n-1]

 sumA = a [0] + a [1] + ... + a [n-1]
 sumASquare = a [0] * a [0] + a [1] * a [1] + a [2] * a [2] + ... + a [n] * a [n]

 sumFirstN =（N *（N + 1））/ 2其中N = n-3所以
 sumFirstN =（n-3）（n-2）/ 2

同样

 sumFirstNSquare = N *（N + 1）*（2 * N + 1）/ 6 =（n-3）（n-2）（2n-5）/ 6

假设重复的元素是= X和Y

所以X + Y = sumA  -  sumFirstN;
 X * X + Y * Y = sumASquare  -  sumFirstNSquare;

所以解决这个二次方，我们可以得到X和Y的价值。
时间复杂度= O（n）
空间复杂度= O（1）

Answer 9

我知道这个问题很老，但是我突然想到了，我想我有一个有趣的答案。 我们知道这是一个谜题和一个简单的解决scheme（即HashMap，sorting等），无论他们多么好，都会很无聊。

由于数字是整数，所以它们具有不变的比特大小（即32）。 让我们假设我们正在使用4位整数。 我们寻找A和B是重复的数字。

我们需要4个桶，每一个一个位。 每个桶包含其特定位为1的数字。例如，桶1获得2,3,4,7，…：

 Bucket 0 : Sum ( x where: x & 2 power 0 == 0 ) ... Bucket i : Sum ( x where: x & 2 power i == 0 ) 

如果没有重复，我们知道每个桶的总和是多less。 我认为这是事先的知识。

一旦产生了上面的桶，其中一堆会比预期的更多的值。 通过构build桶的数量，我们将有（A或B为您的信息）。

我们可以计算（A XOR B）如下：

 A XOR B = Array[i] XOR Array[i-1] XOR ... 0, XOR n-3 XOR n-2 ... XOR 0 

现在回到桶，我们知道哪些桶有我们的数字，哪些桶只有一个（来自XOR位）。

对于只有一个数字的桶，我们可以提取数字num =（和 – 桶的期望总和）。 但是，只有find一个重复的数字，我们才应该是好的，所以如果我们在A或B中至less有一位，我们就得到了答案。

但是如果异或B是零呢？ 那么这种情况是唯一可能的，如果两个重复的号码是相同的号码，那么我们的号码是A或B的答案。

Answer 10

sortingarrays似乎是最好的解决scheme。 一个简单的sorting会使search变得微不足道，而且会占用很less的时间/空间。

否则，如果您知道数字的域，请创build一个包含多个存储桶的数组，并在数组中逐个增加数组。 像这样的东西：

 int count [10]; for (int i = 0; i < arraylen; i++) { count[array[i]]++; } 

然后，只需search您的数组中的任何大于1的数字。这些是重复的项目。 只需要一次通过原始数组，一次通过计数数组。

Answer 11

这里是@ eugensk00的回答（它的一个版本）的Python的实现，它不使用模块化算术。 这是一个单通道algorithm， O（log（n））在空间中 。 如果使用固定宽度（例如32位）整数，则只需要两个固定宽度的数字（例如对于32位：一个64位数字和一个128位数字）。 它可以处理任意大的整数序列（每次读取一个整数，因此整个序列不需要在内存中）。

 def two_repeated(iterable): s1, s2 = 0, 0 for i, j in enumerate(iterable): s1 += j - i # number_of_digits(s1) ~ 2 * number_of_digits(i) s2 += j*j - i*i # number_of_digits(s2) ~ 4 * number_of_digits(i) s1 += (i - 1) + i s2 += (i - 1)**2 + i**2 p = (s1 - int((2*s2 - s1**2)**.5)) // 2 # `Decimal().sqrt()` could replace `int()**.5` for really large integers # or any function to compute integer square root return p, s1 - p 

例：

 >>> two_repeated([2, 3, 6, 1, 5, 4, 0, 3, 5]) (3, 5) 

上面的代码的更详细的版本如下解释：

 def two_repeated_seq(arr): """Return the only two duplicates from `arr`. >>> two_repeated_seq([2, 3, 6, 1, 5, 4, 0, 3, 5]) (3, 5) """ n = len(arr) assert all(0 <= i < n - 2 for i in arr) # all in range [0, n-2) assert len(set(arr)) == (n - 2) # number of unique items s1 = (n-2) + (n-1) # s1 and s2 have ~ 2*(k+1) and 4*(k+1) digits s2 = (n-2)**2 + (n-1)**2 # where k is a number of digits in `max(arr)` for i, j in enumerate(arr): s1 += j - i s2 += j*j - i*i """ s1 = (n-2) + (n-1) + sum(arr) - sum(range(n)) = sum(arr) - sum(range(n-2)) = sum(range(n-2)) + p + q - sum(range(n-2)) = p + q """ assert s1 == (sum(arr) - sum(range(n-2))) """ s2 = (n-2)**2 + (n-1)**2 + sum(i*i for i in arr) - sum(i*i for i in range(n)) = sum(i*i for i in arr) - sum(i*i for i in range(n-2)) = p*p + q*q """ assert s2 == (sum(i*i for i in arr) - sum(i*i for i in range(n-2))) """ s1 = p+q -> s1**2 = (p+q)**2 -> s1**2 = p*p + 2*p*q + q*q -> s1**2 - (p*p + q*q) = 2*p*q s2 = p*p + q*q -> p*q = (s1**2 - s2)/2 Let C = p*q = (s1**2 - s2)/2 and B = p+q = s1 then from Viete theorem follows that p and q are roots of x**2 - B*x + C = 0 -> p = (B + sqrtD) / 2 -> q = (B - sqrtD) / 2 where sqrtD = sqrt(B**2 - 4*C) -> p = (s1 + sqrt(2*s2 - s1**2))/2 """ sqrtD = (2*s2 - s1**2)**.5 assert int(sqrtD)**2 == (2*s2 - s1**2) # perfect square sqrtD = int(sqrtD) assert (s1 - sqrtD) % 2 == 0 # even p = (s1 - sqrtD) // 2 q = s1 - p assert q == ((s1 + sqrtD) // 2) assert sqrtD == (q - p) return p, q 

注意：计算一个数的整数平方根（〜N ** 4）使得上述algorithm是非线性的。

Answer 12

由于指定了范围，您可以执行基数sorting。 这将sorting你的数组在O（n）。 在sorting数组中search重复的是O（n）

Answer 13

你可以使用简单的嵌套for循环

  int[] numArray = new int[] { 1, 2, 3, 4, 5, 7, 8, 3, 7 }; for (int i = 0; i < numArray.Length; i++) { for (int j = i + 1; j < numArray.Length; j++) { if (numArray[i] == numArray[j]) { //DO SOMETHING } } 

* 或者你可以过滤数组，并使用recursion函数，如果你想获得发生的次数 *

 int[] array = { 1, 2, 3, 4, 5, 4, 4, 1, 8, 9, 23, 4, 6, 8, 9, 1,4 }; int[] myNewArray = null; int a = 1; void GetDuplicates(int[] array) for (int i = 0; i < array.Length; i++) { for (int j = i + 1; j < array.Length; j++) { if (array[i] == array[j]) { a += 1; } } Console.WriteLine(" {0} occurred {1} time/s", array[i], a); IEnumerable<int> num = from n in array where n != array[i] select n; myNewArray = null; a = 1; myNewArray = num.ToArray() ; break; } GetDuplicates(myNewArray); 

Answer 14

回答18 ..你正在采取一个数组9，元素是从0开始..因此，最大ele将是6在你的数组。 取0到6的元素之和，并取数组元素的和。 计算它们的差异（比如d）。 这是p + q。 现在从0到6的元素的异或（比如说x1）。 现在采取数组元素的XOR（比如说x2）。 x2是从0到6的所有元素的XOR，除了两个重复的元素，因为它们相互抵消。 现在对于i = 0到6，对于每个ele数组，说p是ele a [i]，所以你可以通过从d中减去这个ele来计算q。 对p和q进行异或运算，并用x2对它们进行XOR运算，并检查x1 == x2。 同样做所有元素，你会得到这个条件将是真实的元素，你完成O（n）。 保持编码！

Answer 15

检查这个… O（n）时间和O（1）空间的复杂性

  for(i=0;i< n;i++) xor=xor^arr[i] for(i=1;i<=n-3;i++) xor=xor^i; 

所以在给出的例子中，你将得到3和5的异或

 xor=xor & -xor //Isolate the last digit for(i = 0; i < n; i++) { if(arr[i] & xor) x = x ^ arr[i]; else y = y ^ arr[i]; } for(i = 1; i <= n-3; i++) { if(i & xor) x = x ^ i; else y = y ^ i; 

}

x和y是你的答案

Answer 16

对于每个数字：检查它是否存在于数组的其余部分。

Answer 17

没有sorting，你将有一个logging你已经访问过的数字。

在psuedocode这基本上会（这样做，所以我不只是给你答案）：

 for each number in the list if number not already in unique numbers list add it to the unique numbers list else return that number as it is a duplicate end if end for each 

Answer 18

这个怎么样：

 for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { if (a[i] == a[j]) { printf("%d appears more than once\n",a[i]); break; } } } 

当然，这不是最快的，但它很简单，易于理解，不需要额外的内存。 如果n是9或100的小数，那么它可能是“最好的”。 （即“最佳”可能意味着不同的事情：最快的执行，最小的内存占用，最可维护，开发成本最低等。）

Answer 19

在c：

  int arr[] = {2, 3, 6, 1, 5, 4, 0, 3, 5}; int num = 0, i; for (i=0; i < 8; i++) num = num ^ arr[i] ^i; 

由于x^x=0 ，重复奇数次的数被中和。 让我们称之为唯一的数字a和a^b 。我们剩下a^b 。 我们知道a^b != 0 ，因为a != b 。 selecta^b任何1位，并将其用作掩码，即selectx作为2的幂，使得x & (a^b)非零。

现在将列表分成两个子列表 – 一个子列表包含y&x == 0所有数字y，剩下的列在另一个子列表中。 顺便说一下，我们selectx，我们知道a和b的对在不同的桶中。 所以我们现在可以独立地将上面使用的相同的方法应用于每个桶，并且发现a和b是什么。

Answer 20

我写了一个小程序，找出不重复的元素的数量，只是通过这个让我知道你的意见，现在我认为偶数个元素是偶数的，但也可以容易地扩展为奇数。

所以我的想法是首先sorting数字，然后应用我的algorithm。快速sorting可以用来sorting这个元素。

让我们拿一个input数组如下

 int arr[] = {1,1,2,10,3,3,4,5,5,6,6}; 

数字2,10和4不重复，但它们是按照sorting顺序排列的，如果没有sorting则使用快速sorting来先sorting出来。

让我们的程序适用于此

 using namespace std; main() { //int arr[] = {2, 9, 6, 1, 1, 4, 2, 3, 5}; int arr[] = {1,1,2,10,3,3,4,5,5,6,6}; int i = 0; vector<int> vec; int var = arr[0]; for(i = 1 ; i < sizeof(arr)/sizeof(arr[0]); i += 2) { var = var ^ arr[i]; if(var != 0 ) { //put in vector var = arr[i-1]; vec.push_back(var); i = i-1; } var = arr[i+1]; } for(int i = 0 ; i < vec.size() ; i++) printf("value not repeated = %d\n",vec[i]); } 

这给出了输出：

 value not repeated= 2 value not repeated= 10 value not repeated= 4 

它简单而直截了当，只是使用XOR的人。

Answer 21

 for(i=1;i<=n;i++) { if(!(arr[i] ^ arr[i+1])) printf("Found Repeated number %5d",arr[i]); } 

Answer 22

这是一个使用顺序统计并在O(n)运行的algorithm。

您可以通过反复调用SELECT作为参数来解决这个问题。

您还要依赖这样一个事实，即在调用SELECT ，小于或等于中位数的元素将移至中位数的左侧。

• 以位数作为参数调用A上的SELECT 。
• 如果中位值是floor(n/2)那么重复值就是中位数。 所以你继续数组的右半部分。
• 否则，如果不是这样的话，重复的值留给中位数。 所以你继续左边的数组。
• 你recursion地继续这种方式。

例如：

• 当A={2, 3, 6, 1, 5, 4, 0, 3, 5} n=9 ，中位数应该是4 。
• 在第一次调用SELECT
• A={3, 2, 0, 1, <3>, 4, 5, 6, 5}中值小于4所以我们继续左半部分。
• A={3, 2, 0, 1, 3}
• 第二次调用SELECT
• A={1, 0, <2>, 3, 3} 1,0,2,3,3 A={1, 0, <2>, 3, 3}那么中位数应该是2 ，所以我们继续右边的一半。
• A={3, 3} ，find了。

该algorithm运行在O(n+n/2+n/4+...)=O(n) 。

Answer 23

那么使用https://en.wikipedia.org/wiki/HyperLogLog ？

Redis提供了http://redis.io/topics/data-types-intro#hyperloglogs

一个HyperLogLog是一个概率数据结构，用来计算唯一的东西（技术上这是指估计一个集的基数）。 通常，计数独特的项目需要使用与要计数的项目数量成比例的内存量，因为您需要记住过去已经看到的元素，以避免多次计数。 然而，有一组交换内存精度的algorithm：在Redis实现的情况下，以一个标准错误的估计值结束，这个值小于1％。 这种algorithm的神奇之处在于，您不再需要使用与计算的项目数量成正比的内存量，而是可以使用恒定的内存量！ 在最坏的情况下是12k字节，或者如果你的HyperLogLog（我们现在称之为HLL）看到了很less的元素，那就less了很多。

Answer 24

我们为什么要试着做math（特别是求解二次方程），这些都是昂贵的操作。 解决这个问题的最佳方法是构造一个大小为（n-3）位的位图，即（n-3）+7 / 8个字节。 最好为这个内存做一个calloc，所以每一位都会被初始化为0。 然后遍历列表并设置特定位为1遇到时，如果该位已设置为1已经为那么那么这是重复的号码。 这可以扩展，以确定是否有任何遗漏数组中没有。 这个解决scheme的时间复杂度是O（n）