在数组中查找重复项
给定一个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); } } }
