Find the two repeating elements
题目描述
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5
The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.
解题方法
1. brute force
2-for loops
Time Complexity: O(n*n)
Auxiliary Space: O(1)
2. count array
count the occurances of each element
Time Complexity: O(n) Auxiliary Space: O(n)
we can get x + y and x * y
(x-y)^2 = x^2 + 2xy + y ^ 2 = (x-y)^2 - 4xy
Time Complexity: O(n)
Auxiliary Space: O(1)
3. two equations
the sum of 1 to n should be n(n+1)/2 the product of 1 to n should be n!
4. XOR
类似find two non repeating elements in a array, 和1 to n XOR，然后找到第一个不是0的bit,然后分成两组再和 1 to n中这一个Bit为1的XOR，得到其中一个，另一个类似方法得到。
5. Use array elements as index
Example: A[] = {1, 1, 2, 3, 2}
i=0;
Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative.
Array now becomes {1, -1, 2, 3, 2}
i=1;
Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition.
i=2;
Check sign of A[abs(A[2])] which is A[2]. A[2] is positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}
i=3;
Check sign of A[abs(A[3])] which is A[3]. A[3] is positive, so make it negative.
Array now becomes {1, -1, -2, -3, 2}
i=4;
Check sign of A[abs(A[4])] which is A[2]. A[2] is negative, so A[4] is a repetition.
Solution