在数组中查找重复的元素O(n)

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

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

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

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

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

这可以在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 = 2aB - A = a + b - (a - b) = 2b

您可以在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],看到它已经是负面的。 你得到重复。

扫描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

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

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

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

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

一个工作scheme:

asume数字是整数

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

 int[] counter = new int[N]; 

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

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

@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 

这是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)中所有元素跳过零的乘积。 我们在两个未知数中有两个方程, XR可以代数地导出。

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

我们来设置:

 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 

你可以按如下步骤进行:

  1. 通过使用线性时间sortingalgorithm(例如计数sorting)对数组进行sorting – O(N)
  2. 扫描已sorting的数组,并在两个连续元素相等时立即停止 – O(N)
 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); } } } } 
  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进行打印设置。

//这与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()); } } 

我们可以有效地使用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)); } } 

这个程序是基于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"); 
  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

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

遍历数组并检查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/

如上所述,

你有一个数字从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)空间;请分享你的想法。
 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]; } }