在数组中查找重复项

给定一个n个整数元素的数组,如何在O(n)时间内查找数组中是否有重复数据,而不使用任何额外的空间。

额外的空间意味着额外的空间O(n)。

Xor操作员是否以任何方式提供帮助。

如果没有额外的信息,这个问题似乎是无法解决的,因为这是元素差异性问题 ,在所需的时间内,您提供的限制是无法解决的。

你可以允许:

(1) 更多的内存,并使用哈希表 / 哈希 集,并符合O(n)时间标准。 [迭代数组,检查一个元素是否在哈希表中,如果是你有傻瓜,否则 – 插入元素到表中,并继续]。

(2) 更多的时间 ,对数组[O(nlogn)]进行sorting并满足子线性空间标准。 [sorting后,遍历数组,并为每个a[i] , a[i+1] ,检查它们是否相同。 如果你没有find一对相同的对子,

编辑 :这个说法的certificate是有点冗长,需要math符号,这里不支持(旁注:我们真的需要tex支持),但这个想法是,如果我们的问题作为一个代数计算树(这是一个公平假定不允许散列,并且在空间不变的情况下),那么Ben或者在他的文章“ 代数计算树的下界”(1983) (在有威望的ACM中发表)中certificate了元素的显着性是在这个下面的Omega(nlogn)问题模型。 卢比表明,同样的结论也适用于限制自己在1991年的整数: 整数元素差异问题的下界 ,但这些文章的结论是,在代数树计算模型 – 整数特征问题是欧米茄(nlogn)问题

随后进行线性扫描

基数sortingalgorithm

根据你实际考虑的基数的时间复杂性,这个解决scheme是O(N)时间,尽pipe我个人的观点不是这样的。 我认为如果你不在整数types上做线性时间的假设,那么问题是无法解决的。

由于sorting在原地,因此只需要O(1)个额外的存储空间。

代码全是C ++ 11

第1步:基数sorting

 template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> void InPlaceRadixSort(std::vector<T>& myArray) { int zerosEnd = -1; int onesBegin = static_cast<int>(myArray.size()); T mask = static_cast<T>(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } 

第2步:线性扫描重复的元素

 for (size_t i=0, j=1; j<myArray.size(); ++i,++j) { if (myArray[i] == myArray[j]) { std::cout << "Found duplicate element " << myArray[i]; } } 

完整的代码

 #include <iostream> #include <string> #include <vector> #include <iostream> #include <vector> #include <algorithm> #include <ctime> #include <type_traits> using namespace std; #define N 10 template <typename T> void PrintArray(const std::vector<T>& myArray) { for (auto&& element : myArray) { std::cout << element << std::endl; } } template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr> void InPlaceRadixSort(std::vector<T>& myArray) { int zerosEnd = -1; int onesBegin = static_cast<int>(myArray.size()); T mask = static_cast<T>(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } int main() { srand(time(NULL)); std::vector<int> myArray(N); for (size_t i=0;i<myArray.size();++i) { myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1); } std::cout << "Vector before radix sort: " << std::endl; PrintArray(myArray); InPlaceRadixSort(myArray); std::cout << "Vector after radix sort: " << std::endl; PrintArray(myArray); for (size_t i=0, j=1; j<myArray.size(); ++i,++j) { if (myArray[i] == myArray[j]) { std::cout << "Found duplicate element " << myArray[i]; } } return 0; } 

现场演示

这个问题有一个有趣的解决scheme ,单个约束的元素应该在0到n-2(含)之间,其中n是元素的数量。

这在O(n)时间内以O(1)空间复杂度工作。

这是O(n)时间使用和O(1)空间使用的解决scheme!

 Traverse the array. Do following for every index i of A[]. { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // ie, A[abs(A[i])] is negative this element (ith element of list) is a repetition } 

积分:方法5 极客的极客

这个解决scheme基于通过@dsimcha从数组中删除重复项的方法,正如可以在这里find的那样。

它执行就地交换algorithm,使用值散列值交换位置。 请注意,这在一定程度上破坏了原始数组内容。 但是在OP的问题上没有要求禁止这一点。

 public static class DupFinder { public static bool HasDups(int[] array, ref int nEvals) { nEvals = 0; return DupFinder.FindInPlace(array, 0, ref nEvals); } private static bool FindInPlace(int[] array, int start, ref int nEvals) { if (array.Length - start < 2) return false; var sentinel = array[start]; var offset = start + 1; var len = array.Length - offset; for (var ndx = 0; ndx < len; nEvals++) { var cur = array[offset + ndx]; if (cur == sentinel) { ndx++; continue; } var hash = cur % len; if (ndx == hash) { ndx++; continue; } var at_hash = array[offset + hash]; if (cur == at_hash) { array[offset + ndx] = sentinel; ndx++; continue; } if (at_hash == sentinel) { Swap(array, offset, ndx, hash); ndx++; continue; } var hash_hash = at_hash % len; if (hash_hash != hash) { Swap(array, offset, ndx, hash); if (hash < ndx) ndx++; } else { ndx++; } } var swapPos = 0; for (var i = 0; i < len; i++, nEvals++) { var cur = array[offset + i]; if (cur != sentinel && i == (cur % len)) Swap(array, offset, i, swapPos++); } for (var i = swapPos; i < len; nEvals++) { var cur = array[offset + i]; if (cur == sentinel) return true; // got dups. else i++; } // Let's assume C# supports tail recursion ;-) // Then => look ma, O(1) extra storage space. return FindInPlace(array, offset + swapPos, ref nEvals); } private static void Swap(int[] array, int offset, int first, int second) { var tmp = array[offset + first]; array[offset + first] = array[offset + second]; array[offset + second] = tmp; } } 

因此,如果我们暂时假设c#支持尾recursion,并且我们不把所使用的栈帧作为额外的空间来计数,那么它具有O(1)空间要求。

作者提到它具有O(N)时间复杂性。 我已经执行的(有限)testing(与计算复杂度分析相对)将表明它更接近O(N log N)。

 Array Size Dup Position #Evals 12 7 26 12 - 35 100,000 80,000 279,997 100,000 - 453,441 

对于一般情况,这个问题似乎没有一个解决scheme,由于复杂的约束和无限制的input。

很明显,你甚至需要至lessN步才能看到所有的input。 所以它不能比O(n) 更快

现在,为了确保find每一个可能的重复,你有不同的可能性:

  • 比较每个数字与其他数字,这不需要太多额外的空间,但需要O(n^2)
  • 通过更换可用空间中的整数,以更智能的方式进行比较。 这允许在存储序列中“存储信息”。 实际上,比较所有的数字通常是在sortingalgorithm中完成的。 已知最快的sortingalgorithm不需要额外的空间,需要O(n log n)时间。 维基百科有一个相当长的写法,有很多来源 。 所以你永远不可能以这种方式得到你的时间要求。 ( 一些已知sortingalgorithm的比较图 )
  • 你可以用一个散列图做一些logging,这个散列图可以让你只用线性时间O(n) ,但是这个logging需要存储在某个地方 。 否则,你只会“忘记”你已经看到的数字。 不幸的是,如果你的input增加,记账将需要更多的空间,因为你有许多不同的数字要记住。 所以不可能有相同的固定数量的内存和比较任意长的input序列。 因此,你将不得不违反恒定的空间O(1)

正如@Atishay在他的回答中指出的那样,如果您的投入非常有限, 可以有一个解决scheme。 这里需要你有一个大小为n的数组,可能的值只在[0,n-2]的范围内。 这个要求保证必须在某处重复,因为与数组中元素的值不同。 有了这些知识和非常具体的价值观,你就可以做到。 但是这使用了非常狭窄的假设,并没有解决问题中提出的一般问题。

编辑

正如在评论中所阐明的那样,基于比较的sortingalgorithm的时间复杂性certificate了一个下界。 作为参考,请看这里:

布隆filter是一个空间高效的哈希集合,具有可调的误报率。 假阳性的可能性意味着你必须返回并检查一个真正的副本,当你从BF获得命中时,引入一个N ^ 2项 – 但系数是〜exp( – (用于filter的额外空间))。 这产生了一个有趣的空间与时间的权衡空间。

我没有证据表明这个问题是不可解释的,但总的来说,“这里有一个有趣的权衡空间”是一个不可解决的问题的好答案。

一个使用单个int作为临时variables的实现..这是使用位向量/

  public static boolean isUniqueChars(String str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) - 'a'; if ((checker & (1 << val)) > 0) return false; checker |= (1 << val); } return true; } 

或者我的prev实现O(n ^ 2)而不使用任何临时variables

 public static bool isDuplicate(char[] str) { if (str == null) return false; int len = str.length; if (len < 2) return false; for (int i = 1; i < len; ++i) { for (int j = 0; j < len; ++j) { if (str[i] == str[j]) return true; } } return false; } 

干净的例子用O(n)按时间和O(1)按空间确定重复项:

 public class DuplicateDetermineAlgorithm { public static boolean isContainsDuplicate(int[] array) { if (array == null) { throw new IllegalArgumentException("Input array can not be null"); } if (array.length < 2) { return false; } for (int i = 0; i < array.length; i++) { int pointer = convertToPositive(array[i]) - 1; if (array[pointer] > 0) { array[pointer] = changeSign(array[pointer]); } else { return true; } } return false; } private static int convertToPositive(int value) { return value < 0 ? changeSign(value) : value; } private static int changeSign(int value) { return -1 * value; } } 
 public static void getDuplicatesElements (Integer arr[]){ //Status array to track the elements if they are already considered boolean status[] = new boolean [arr.length]; //Flag to mark the element found its duplicate boolean dupFlag = false; //Output string String output = ""; //Count of duplicate elements found int count = 0; //Initialize status array with all false ie no duplicates for (int i = 0; i < arr.length; i++) { status[i] = false; } //first loop to check every element for (int i = 0; i < arr.length - 1; i++) { //Initialize every element to no duplicate dupFlag = false; //Check if this element is not already found duplicate, if not, check now. if (!status[i]){ for (int j = i+1; j < arr.length; j++){ if (arr[i] == arr[j]){ dupFlag = true; status[j] = true; } } } if (dupFlag){ output = output + " " + arr[i]; count++; } } System.out.println("Duplicate elements: " + output ); System.out.println("Count: " + count ); } 

放弃

我没有答案,但我的想法太广泛,不能评论。 另外,我想把它们写下来,所以我花三个小时考虑一个解决scheme并不是完全浪费。 我希望给你一个不同的观点,但是如果你不喜欢浪费时间,就不要继续读下去。 或者只是投下这个答案,这是值得的:)

要启动我们的视觉思维,让我们有一个示例数组: 50 100 150 -2 -1 0 1 2 3 4 。 正如你可以肯定的说,它没有重复,所以我们的algorithm应该输出FALSE 。 另外,它的长度是10

步骤A:计算O(N)时间

现在让我们忽略额外的内存约束(实际上,通过假设我们可以拥有O(\inf)额外的内存:)实际上违反了它,并保存在一个虚构的无限数组中(它也是双重无限的,因为它允许负数也是)每个整数的计数。 对于我们的input,这个数组看起来像这样:

 ...000001111111000...00100...00100...001000000... ^ ^ ^ [index -2] [index 50] [index 150] 

如果数组中的任何元素大于1 ,那么我们有一个重复的algorithm应该返回TRUE

步骤B:在O(N)时间内将-inf ..inf映射到0..N

假设我们有一个映射f(x):-inf..inf -> 0..N ,它可以将我们的无限数组压缩成一个大小为N的数组,并且在O(N)时间内执行。 这就是哈希理想的做法。 请注意,我们不关心维护数组的顺序,因为我们只关心它是否具有高于1的元素。因此,我们可以将这两个步骤结合起来,并消除无限的内存需求 – 耶! 我们仍然使用额外的O(N)内存(实际上,正好N个计数)来保持计数值。 下一步将摆脱这一点。

步骤C:使用第一个元素作为开关

在我解释这一步之前,请注意,我们并不需要存储大于1的任何计数。第一次我们想增加一个计数器,并且我们注意到它已经具有1的值,我们知道我们发现了一个重复! 所以每个计数器的1位内存就足够了。 这将所需的内存减less到O(lg(N)),但是我们并不关心这个,因为它不够好。 重要的部分是每个计数器的1位内存就足够了。

我们现在要利用我们可以修改input数组的事实。 我们遍历数组,并用第一个元素的值对所有元素进行xor 。 如果结果小于操作前的值,我们将其更改为该结果。 我们还将第一个元素单独存储为sw ,额外的O(1)内存开销。

现在,我们可以使用存储的第一个元素sw和变换后的数组按照以下方式对来自计数步骤(步骤A + B)的计数进行编码:考虑具有A索引k的元素,如果A[f(A[k])] < A[f(A[k])] xor sw我们正在考虑的元素 – A[k] – 以前没有见过,所以我们改变A[f(A[k])] A[f(A[k])] < A[f(A[k])] xor sw A[f(A[k])]A[f(A[k])] xor sw 。 否则,如果A[f(A[k])] > A[f(A[k])] xor sw那么计数就是我们正在考虑的元素 – A[k] – 之前已经看到,所以它是重复的。

假设地图:

 f(-2 xr 50) -> 0 f(-1 xr 50) -> 1 f(0) -> 2 f(1) -> 3 f(2) -> 4 f(3) -> 5 f(4) -> 6 f(86) -> 7 f(150) -> 8 f(1337) -> 9 

并按以下顺序执行步骤之后: step c; step a+b step c; step a+binput数组看起来像这样:

 50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory] 0 86 150 -2 xr 50 -1 xr 50 0 1 2 3 4 [state after step c] 0 86 *164* -2 xr 50 -1 xr 50 0 1 2 3 4 [counted element 0] 0 86 164 -2 xr 50 -1 xr 50 0 1 *48* 3 4 [counted element 1] 0 86 164 -2 xr 50 -1 xr 50 0 1 48 *49* 4 [counted element 2] *50* 86 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 3] 50 *100* 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 4] 50 100 !164! -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 5] 

试图计数索引为5元素为0我们看到数组中已经有一个0了! (因为A[f(A[5])]164 ,它大于164 xr 50 )所以我们输出TRUE ,algorithm结束。

故事的道德启示

如果我们没有足够的memory x time我们必然会忘记一些事情,犯错误。

抱歉

不幸的是,我们没有一个完美的散列函数,我们不能仅仅凭空创build内存,所以传统的方法在所需的约束条件下是不行的。 由OP给出的答案指向的algorithm可能会被修改,以便允许使用解释为数组元素的数字落在数组边界之外,给定一个完美的散列函数。 但即使如此,它必须发明如何使用它来检测重复,而不是find一个guaraneed存在…

无论如何,有趣的问题。

 import java.util.HashSet; import java.util.Set; public class FindDups { public static void main(String[] args) { int a[]={1,2,3,3,4}; Set<Integer> s=new HashSet<Integer>(); for(int i=0;i<a.length;i++) { if(!s.add(a[i])) System.out.println("at index"+ i+" "+a[i]+"is duplicate"); } for(int i:s) { System.out.println(i); } } }