bohu88
BAN USER
Comments (4)
Reputation -5
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
1. Find all pairs of sum c = a + b, a is from the first array and b is from the second array ----- this cost O(N^2);
2. Sort the set which contains all the pair sum using radix sort. It costs O(N^2);
3. Find the common elements between the sorted array in step 2 and the first array or the second array by merging.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
There is actually a O(N) algorithm. Suppose the input is data[1...n]. We make a new array which is called count[1...n]. count[i] means the amount difference between 0s and 1s for data[1...i]. If (i,j) is a interval in which the number of 0s and 1s are the same, then count[i]=count[j]. So we just apply radix sort to sort count[1...n] and to find all the identical values in count[1...n]. Radix sort is O(N).
- bohu88 December 14, 2011