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

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

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

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

PS [你不应该使用sorting]

如果您知道可能的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; 

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

好吧,似乎我只是不能给它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中出现两次。

你知道你的数组包含从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

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

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

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

在这个主题上检查这个旧的,但很好的论文:

  • 查找重复元素 (PDF)

一些问题的答案: 确定数组是否包含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 )。

 假设数组是

 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)

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

由于数字是整数,所以它们具有不变的比特大小(即32)。 让我们假设我们正在使用4位整数。 我们寻找AB是重复的数字。

我们需要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的答案。

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

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

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

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

这里是@ 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是非线性的。

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

你可以使用简单的嵌套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); 

回答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)。 保持编码!

检查这个… 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是你的答案

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

没有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 

这个怎么样:

 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的小数,那么它可能是“最好的”。 (即“最佳”可能意味着不同的事情:最快的执行,最小的内存占用,最可维护,开发成本最低等。)

在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是什么。

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

所以我的想法是首先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的人。

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

这是一个使用顺序统计并在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)

那么使用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了很多。

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