The Smallest Difference(Medium)

From lintcode

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i] and B[j] (|A[i] - B[j]|) is as small as possible, return their smallest difference.

Example

For example, given array A = [3,6,7,4], B = [2,8,9,3], return 0 Challenge

O(n log n) time

先对A，B排序，然后分别赋指针p1，p2。以两个指针都不越界为条件遍历。若p1 <= p2，更新当前差值，p1++；反之，则更新差值并令p2++。

public int smallestDifference(int[] A, int[] B) {
        int p1 = 0, p2 = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int res = Integer.MAX_VALUE;
        while (p1 < A.length && p2 < B.length) {
            if (A[p1] <= B[p2]) {
                res = Math.min(res, B[p2] - A[p1]);
                p1++;  
            }
            else {
                res = Math.min(res, A[p1] - B[p2]);
                p2++;
            }
        }
        return res;
    }