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.
Method 1 (Use Count array)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.
void findRepeating(int arr[], int size) { int *count = (int *)calloc(sizeof(int), (size - 2)); int i; printf(" Repeating elements are "); for(i = 0; i < size; i++) { if(count[arr[i]] == 1) printf(" %d ", arr[i]); else count[arr[i]]++; } }
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 2 (Use XOR)
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.
The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.
void findRepeating(int arr[], int size) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single set bit of xor */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for(i = 1; i < size; i++) xor ^= arr[i]; for(i = 1; i <= n; i++) xor ^= i; /* Get the rightmost set bit in set_bit_no */ set_bit_no = xor & ~(xor-1); /* Now divide elements in two sets by comparing rightmost set bit of xor with bit at same position in each element. */ for(i = 0; i < size; i++) { if(arr[i] & set_bit_no) x = x ^ arr[i]; /*XOR of first set in arr[] */ else y = y ^ arr[i]; /*XOR of second set in arr[] */ } for(i = 1; i <= n; i++) { if(i & set_bit_no) x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */ } printf("\n The two repeating elements are %d & %d ", x, y); }
Time Complexity: O(n)
Auxiliary Space: O(1)
更好理解的java版本:
A[i]: 3,2,2,3,4,1
i: 0,1,2,3,4,5
j: 0,1,2,3,4,0
X = X ^ A[i] ^ j, 循环之后的X的结果就是重复的两个数2,3的异或。
public void findTwoRepeatingNumbers(int[] A) { int x = 0; for(int i=0; i<A.length; i++) { int j = (i!=A.length-1) ? i : 0; x ^= A[i] ^ j; } int lsb = x & -x; int a = 0, b = 0; for(int i=0; i<A.length; i++) { if((A[i]&lsb) == lsb) { a ^= A[i]; } else { b ^= A[i]; } int j = (i!=A.length-1) ? i : 0; if((j&lsb) == lsb) { a ^= j; } else { b ^= j; } } System.out.println("a="+a + ", b="+b); }
Method 3 (Use array elements as index)
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 // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
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.
Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.
void findRepeating(int arr[], int size) { int i; printf("\n The repeating elements are"); for(i = 0; i < size; i++) { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else printf(" %d ", abs(arr[i])); } }
Reference:
http://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/
相关推荐
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
This article includes how to convert any array into a column vector, bounding a value without if statements, and repeating/tiling a vector without repmat. Contents: * The Profiler * Array ...
Repeating elements 77 Replacing elements 77 Reversing elements 78 Searching a list 79 Editing a list 81 Sorting a list 82 Splitting a string into a list 83 Chapter 6: The Tcl Dictionary 85 ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
In general, the time to process a given command is short except for the following operations: ?filter initialization ?wavelength selection ?palette definition The first of these is quite lengthy (30 ...
The PHY Interface for the PCI Express Architecture (PIPE) is intended to enable the development of functionally equivalent PCI Express PHY's. Such PHY's can be delivered as discrete IC's or as ...
A simple program that generates non repeating numbers at random in certain ranges.
array.zip A simple program that shows how a two-dimensional array works within a VB program.<END><br>70,Bubblesort.zip A simple Bubble Sort code that shows how the program works within a VB ...
Given the choice between repeating an action over and over for an hour, or writing a script to automate it, these people will choose the script every time. Call it productivity or just stubbornness...
This new edition has been extended to include two additional Bonus Day lessons, with emphasis on the year 2000 problem. In many cases, it is difficult to illustrate a programming point by using a ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3.
The array Module 420 The numarray Package 422 Using Arrays 422 Computing the Standard Deviation 423 Summary 424 Exercises 425 02_596543 ftoc.qxd 6/29/05 10:55 PM Page xxiii xxiv Contents Chapter...
developers usually have to carry out a range of common tasks: communicating information to a user, displaying pop-up windows, showing repeating information in a tabular or grid layout, ...
an equal number of times, or if there was a bias in the number of mentions. Imagine the subtitles of what the announcers were saying as your input stream of data. You could have a spout that reads ...
Repeating the first grade: How the decision is made Psychologv in rhr Schools Volume 21, Ocroher, 1984 FIRST-GRADE PROMOTIONAL PRACTICES: IMPLICATIONS FOR THE SCHOOL PSYCHOLOGIST'S ROLE: A ...
Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先...
Stein presents full, working scripts, calling attention to particularly interesting lines and passages by repeating them in the text. If a program makes use of an unusual or previously undiscussed ...
The specification defines a set of PHY functions which must be incorporated in a PIPE compliant PHY, and it defines a standard interface between such a PHY and a Media Access Layer (MAC) & Link Layer...
DBAs, database designers, DBMS implementers, application developers, and database professors and students can find the information they need on a daily basis, information that isn’t readily ...