the_one
BAN USERhow about a simpler approach of using divide of merge sort. keep sub dividing the set of rectangles till 1 rectangle remains. checking if a point is inside the rectangle is constant time operation.
there is no need to combine as the result is unique rectangle.
as a optimization , we can have global variable which says the search is complete. before we check for any inside condition for a rectangle we simply check if this variable is set. this will minimize the containment operation.
public static void printCommonElements(int a[], int b[]){
int aIdx = 0, bIdx = 0;
int count = 0;
boolean isMatch = false;
while(aIdx < a.length && bIdx < b.length){
count = 0;
isMatch = false;
while(aIdx < a.length-1 && a[aIdx + 1] == a[aIdx])
aIdx++;
if(b[bIdx] == a[aIdx]){
isMatch = true;
count++;
}
while(bIdx <b.length-1 && b[bIdx+1] == b[bIdx]){
bIdx++;
if(isMatch)
count++;
}
for(int i = 0 ; i < count; i++)
System.out.print(b[bIdx] + " ");
aIdx++; bIdx++;
}
}
- the_one February 11, 2013public static void printRepeatedAndMissingNumber(int arr[]){
int i = 0;
while(i<arr.length){
while(arr[i]-1 != i && arr[i] != -1){
if(arr[i] == arr[arr[i] - 1 ]){
System.out.println("repeated = " + arr[i]);
arr[i] = -1;
i++;
}
else{
int temp = arr[arr[i]-1];
arr[arr[i]-1] = arr[i];
arr[i] = temp;
}
}
i++;
}
for(i = 0; i <arr.length;i++){
if(arr[i] == -1) System.out.println("missing =" + (i+ 1));
}
}
i am not really sure if this is O(n) time complexity
the question does not say to store the duplicate elements. so we can simply print them as encountered. which can eliminate the output array. also my previous comment regarding the output may not be entirely wrong. in case the question is slightly modified and it is said from which array we need to print all duplicate elements. the solution i gave below is doing that except it always chooses from second array. this can be easily tweaked
- the_one February 12, 2013