public class MinDifference {
public static int findMinDifference(int[] A, int[] B) {
int min = Integer.MAX_VALUE;
// Go through A and find adjacent differences
for( int i = 0; i < A.length-1; i++ ) {
min = MIN( min, Math.abs(A[i] - A[i+1]) );
}
// Go through B and find adjacent differences
for( int i = 0; i < B.length-1; i++ ) {
min = MIN( min, Math.abs(B[i] - B[i+1]) );
}
// Find minimum differences between both arrays
if( A.length <= B.length ) {
for( int i = 0; i < A.length; i++ ) {
int index = findIndexFor(B, A[i]); // Find where A[i] would be in B
min = MIN( min, Math.abs(A[i] - B[index]) );
}
} else {
for( int i = 0; i < B.length; i++ ) {
int index = findIndexFor(A, B[i]); // Find where B[i] would be in A
min = MIN( min, Math.abs(B[i] - A[index]) );
}
}
return min;
}
// Binary search
private static int findIndexFor( int[] arr, int elem ) {
int l = 0, m = arr.length/2, r = arr.length - 1;
while( l < r ) {
m = (l+r)/2;
if( elem < arr[m] ) {
r = m - 1;
} else if ( elem > arr[m] ) {
l = m + 1;
} else { // elem == arr[m]
return m;
}
}
return r;
}
private static int MIN( int a, int b ) {
return (a < b)? a : b;
}
public static void main(String[] args) {
int[] A = {1, 4, 7, 10, 19};
int[] B = {-3, 12, 15, 23, 26, 30, 33, 36, 40};
System.out.println("Minimum Diff: " + findMinDifference(A,B));
}
}
Thursday, May 28, 2015
L Question: Min Difference Between Two Arrays
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment