在数组中查找重复的元素O（n）

我在求职面试中被问到这个问题，我一直在思考正确的答案。

你有一个数字从0到n-1的数组，其中一个数字被删除，并被数组中已经存在的一个数字replace，这个数字就是该数字的一个副本。 我们如何在O（n）时间检测到这个重复？

例如，一个1,2,3,4的数组将变成1,2,2,4 。

时间O（n ² ）的简单解决scheme是使用嵌套循环来查找每个元素的副本。

Answer 1

我们有原始数组int A[N]; 创build第二个数组bool B[N] ，types为bool=false 。 迭代第一个数组并设置B[A[i]]=true如果是false，否则bing！

Answer 2

这可以在O(n)时间和O(1)空间中完成。

（该algorithm仅适用，因为数字是已知范围内的连续整数）：

在通过vector的一次通过中，计算所有数字的总和，以及所有数字的平方和。

从N(N-1)/2减去所有数字的总和。 叫这个A

从N(N-1)(2N-1)/6减去平方和。 除以A 调用结果B

被删除的数字是(B + A)/2 ，被replace的数字是(B - A)/2 。

例：

向量是[0, 1, 1, 2, 3, 5] ：

• N = 6

• vector之和为0 + 1 + 1 + 2 + 3 + 5 = 12，N（N-1）/ 2为15.A = 3。

• N（N-1）（2N-1）/ 6的平方为0 + 1 + 1 + 4 + 9 + 25 = 40.B =（55-40）/ A = 5。

• 被删除的数字是（5 + 3）/ 2 = 4。

• 它被replace的数字是（5 – 3）/ 2 = 1。

为什么它的作品：

• 原vector[0, ..., N-1]为N(N-1)/2 。 假设值a已被删除并由b取代。 现在修改后的vector的和将是N(N-1)/2 + b - a 。 如果我们从N(N-1)/2减去修改后的向量的和，我们得到a - b 。 所以A = a - b 。

• 类似地，原始vector的平方和为N(N-1)(2N-1)/6 。 修改后的向量的平方和为N(N-1)(2N-1)/6 + b 2 - a 2 。 从原始总和中减去修改后的向量的平方和，得到a 2 - b 2 ，它与(a+b)(ab) 。 所以如果我们把它除以a - b （即A ），我们得到B = a + b 。

• 现在B + A = a + b + a - b = 2a和B - A = a + b - (a - b) = 2b 。

Answer 3

您可以在O（N）时间内完成，无需额外的空间。 algorithm的工作原理如下：

按以下方式遍历数组：

1. 对于遇到的每个元素，将其对应的索引值设置为负值。 例如：如果你发现一个[0] = 2。得到一个[2]并且否定这个值。

   通过这样做你可以标记它遇到。 既然你知道你不能有负数，你也知道你是否定它的人。

2. 检查对应于该值的索引是否已被标记为负数，如果是，则获取重复的元素。 例如：如果a [0] = 2，则转到[2]并检查是否为负数。

可以说你有以下数组：

 int a[] = {2,1,2,3,4}; 

第一个元素后，你的数组将是：

 int a[] = {2,1,-2,3,4}; 

第二个元素后，你的数组将是：

 int a[] = {2,-1,-2,3,4}; 

当你到达第三个元素，你去一个[2]，看到它已经是负面的。 你得到重复。

Answer 4

扫描arrays3次：

1. 将所有数组元素XOR在一起 – > A 将0到N-1 – > B所有数字XOR在一起。 现在A XOR B = X XOR D ，其中X是被移除的元素，D是重复的元素。
2. selectA XOR B任何非零位。 把这个位设置的所有数组元素XOR在一起 – > A1 。 将此位设置的所有数字从0到N-1“异或”（ B1 。 现在要么A1 XOR B1 = X要么A1 XOR B1 = D
3. 再次扫描arrays并尝试find A1 XOR B1 。 如果发现，这是重复的元素。 如果不是，则重复元素是A XOR B XOR A1 XOR B1 。

Answer 5

我build议使用一个BitSet。 我们知道N对于数组索引是足够小的，所以BitSet的大小是合理的。

对于数组的每个元素，检查与其值相对应的位。 如果已经设置，那是重复的。 如果没有，请设置位。

Answer 6

使用HashSet来保存已经看到的所有数字。 它运行在（分期偿还） O(1)时间，所以总数是O(N) 。

Answer 7

使用散列表。 在哈希表中包含一个元素是O（1）。

Answer 8

一个工作scheme：

asume数字是整数

创build一个数组[0 .. N]

 int[] counter = new int[N]; 

然后迭代读取并递增计数器：

  if (counter[val] >0) { // duplicate } else { counter[val]++; } 

Answer 9

@rici对时间和空间的使用是正确的：“这可以在O（n）时间和O（1）空间中完成。

然而，这个问题可以扩大到更广泛的要求：没有必要只有一个重复号码，数字可能不连续。

OJ这样说：（注3显然可以缩小）

给定一个包含n + 1个整数（其中每个整数介于1和n（含）之间）的数组numn，certificate至less有一个重复数字必须存在。 假设只有一个重复号码，find重复号码。

注意：

• 您不得修改数组（假定该数组是只读的）。
• 您必须只使用恒定的O（1）额外空间。
• 你的运行时复杂度应该小于O（n2）。
• 数组中只有一个重复数字，但可以重复多次。

Keith Schwarz使用Floyd的循环寻找algorithm对这个问题进行了很好的解释和回答：

我们需要用来解决这个问题的主要技巧是注意到，因为我们有一个从0到n-2范围内的n个元素的数组，所以我们可以把数组看作是从集合{0,1， …，n – 1}自身。 这个函数由f（i）= A [i]定义。 给定这个设置，重复值对应于一对指数i！= j，使得f（i）= f（j）。 因此，我们的挑战是find这一对（我，j）。 一旦我们有了它，我们可以通过selectf（i）= A [i]很容易地find重复值。

但是我们如何才能find这个重复的价值呢？ 事实certificate，这是一个在计算机科学中被广泛研究的称为循环检测的问题。 问题的一般forms如下。 我们给了一个函数f。 定义序列x_i as

  x_0 = k (for some k) x_1 = f(x_0) x_2 = f(f(x_0)) ... x_{n+1} = f(x_n) 

假设f从一个域映射到它自己，这个函数将有三种forms之一。 首先，如果域是无限的，那么序列可以是无限长且不重复的。 例如，整数上的函数f（n）= n + 1有这个属性 – 没有重复的数字。 其次，序列可能是一个闭环，这意味着有一些我，所以x_0 = x_i。 在这种情况下，序列无限期地循环一些固定的值。 最后，序列可以是“rho-shaped”。 在这种情况下，序列看起来像这样：

  x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} ^ | | | +-----------------------+ 

也就是说，序列从进入一个循环的一系列元素开始，然后无限循环。 我们将表示在循环的“入口”序列中达到的循环的第一个元素。

一个python实现也可以在这里find：

 def findDuplicate(self, nums): # The "tortoise and hare" step. We start at the end of the array and try # to find an intersection point in the cycle. slow = 0 fast = 0 # Keep advancing 'slow' by one step and 'fast' by two steps until they # meet inside the loop. while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break # Start up another pointer from the end of the array and march it forward # until it hits the pointer inside the array. finder = 0 while True: slow = nums[slow] finder = nums[finder] # If the two hit, the intersection index is the duplicate element. if slow == finder: return slow 

Answer 10

这是O(n)时间和O(1)空间的替代解决scheme。 这与rici的相似。 我觉得它更容易理解，但在实践中，它会更快地溢出。

设X是缺less的数字， R是重复的数字。

1. 我们可以假设数字是从[1..n] ，即零不出现。 实际上，在循环数组的时候，我们可以testing是否find零，如果不是，则立即返回。

2. 现在考虑：

    sum(A) = n (n + 1) / 2 - X + R product(A) = n! R / X 

product(A)是product(A)中所有元素跳过零的乘积。 我们在两个未知数中有两个方程， X和R可以代数地导出。

编辑 ：由大众需求，这是一个成功的例子：

我们来设置：

 S = sum(A) - n (n + 1) / 2 P = n! / product(A) 

然后我们的方程变成：

 R - X = S X = RP 

这可以解决：

 R = S / (1 - P) X = PR = PS / (1 - P) 

例：

 A = [0 1 2 2 4] n = A.length - 1 = 4 S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1 P = 4! / (1 * 2 * 2 * 4) = 3 / 2 R = -1 / (1 - 3/2) = -1 / -1/2 = 2 X = 3/2 * 2 = 3 

Answer 11

你可以按如下步骤进行：

1. 通过使用线性时间sortingalgorithm（例如计数sorting）对数组进行sorting – O（N）
2. 扫描已sorting的数组，并在两个连续元素相等时立即停止 – O（N）

Answer 12

 public class FindDuplicate { public static void main(String[] args) { // assume the array is sorted, otherwise first we have to sort it. // time efficiency is o(n) int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 }; int count = 1; int element1; int element2; for (int i = 0; i < elementData.length - 1; i++) { element1 = elementData[i]; element2 = elementData[count]; count++; if (element1 == element2) { System.out.println(element2); } } } } 

Answer 13

  public void duplicateNumberInArray { int a[] = new int[10]; Scanner inp = new Scanner(System.in); for(int i=1;i<=5;i++){ System.out.println("enter no. "); a[i] = inp.nextInt(); } Set<Integer> st = new HashSet<Integer>(); Set<Integer> s = new HashSet<Integer>(); for(int i=1;i<=5;i++){ if(!st.add(a[i])){ s.add(a[i]); } } Iterator<Integer> itr = s.iterator(); System.out.println("Duplicate numbers are"); while(itr.hasNext()){ System.out.println(itr.next()); } } 

首先使用Scanner类创build一个整数数组。 然后遍历数字循环，并检查数字是否可以添加到设置（数字可以添加设置只有当该特定的数字不应该已经设置，意味着集合不允许重复号添加并返回一个布尔值如果添加重复值，则VAL错误）。如果没有。 不能被添加意味着它是重复的，所以将重复的数字添加到另一个集合，以便我们可以稍后打印。 请注意，我们正在将重复数字添加到一个集合中，因为可能重复的数字可能会重复多次，因此只能添加一次。最后，我们使用Iterator进行打印设置。

Answer 14

//这与HashSet方法类似，但只使用一个数据结构：

  int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 }; LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(); for (int i : a) { map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1); } Set<Entry<Integer, Integer>> es = map.entrySet(); Iterator<Entry<Integer, Integer>> it = es.iterator(); while (it.hasNext()) { Entry<Integer, Integer> e = it.next(); if (e.getValue() > 1) { System.out.println("Dupe " + e.getKey()); } } 

Answer 15

我们可以有效地使用hashMap：

 Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,}; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int x : a) { if (map.containsKey(x)) map.put(x,map.get(x)+1); else map.put(x,1); } Integer [] keys = map.keySet().toArray(new Integer[map.size()]); for(int x : keys) { if(map.get(x)!=1) { System.out.println(x+" repeats : "+map.get(x)); } } 

Answer 16

这个程序是基于C＃的，如果你想用另一种编程语言来做这个程序，你必须首先改变一个数组的顺序，并把第一个元素和第二个元素进行比较。如果相等，那么find重复的数字。程序是

 int[] array=new int[]{1,2,3,4,5,6,7,8,9,4}; Array.Sort(array); for(int a=0;a<array.Length-1;a++) { if(array[a]==array[a+1] { Console.WriteLine("This {0} element is repeated",array[a]); } } Console.WriteLine("Not repeated number in array"); 

Answer 17

1. sorting数组O（n ln n）

2. 使用滑动窗口技巧来遍历数组O（n）

   空间是O（1）

    Arrays.sort(input); for(int i = 0, j = 1; j < input.length ; j++, i++){ if( input[i] == input[j]){ System.out.println(input[i]); while(j < input.length && input[i] == input[j]) j++; i = j - 1; } } 

testing用例int [] {1,2,3，7，7，8，3,5,7,1,2,7}

输出1，2，3，7

Answer 18

这个问题可能是一样的问题， check whether there is a circle in the array ， 这里有一个很好的链接来解决它。

Answer 19

遍历数组并检查array[abs(array[i])]的符号，如果为正则为负数，如果为负数，则打印它，如下所示：

 import static java.lang.Math.abs; public class FindRepeatedNumber { private static void findRepeatedNumber(int arr[]) { int i; for (i = 0; i < arr.length; i++) { if (arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else { System.out.print(abs(arr[i]) + ","); } } } public static void main(String[] args) { int arr[] = { 4, 2, 4, 5, 2, 3, 1 }; findRepeatedNumber(arr); } } 

参考： http : //www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

Answer 20

如上所述，

你有一个数字从0到n-1的数组，其中一个数字被删除，并被数组中已经存在的一个数字replace，这个数字就是该数字的一个副本。

我假设arrays中的元素sorting，除了重复的条目。 如果是这样的情况，我们可以很容易地实现这个目标如下：

  public static void main(String[] args) { //int arr[] = { 0, 1, 2, 2, 3 }; int arr[] = { 1, 2, 3, 4, 3, 6 }; int len = arr.length; int iMax = arr[0]; for (int i = 1; i < len; i++) { iMax = Math.max(iMax, arr[i]); if (arr[i] < iMax) { System.out.println(arr[i]); break; }else if(arr[i+1] <= iMax) { System.out.println(arr[i+1]); break; } } } 

• O（n）时间和O（1）空间;请分享你的想法。

Answer 21

 int a[] = {2,1,2,3,4}; int b[] = {0}; for(int i = 0; i < a.size; i++) { if(a[i] == a[i+1]) { //duplicate found //copy it to second array b[i] = a[i]; } }