The Smallest Difference 387

Question

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

Solution

分别对两个数组排序，然后从两个数组最小的元素开始比较，更新最小值。因为两个数组是赠序排列，增大较小的那个数才有可能缩小两者的差值，因此每次将较小的那个数移动一位。当一个数组为空时，表明已经不可能再增大，此时的差值已经是能达到的最小。

时间复杂度O(nlogn)。

代码如下：

public class Solution {
    /**
     * @param A, B: Two integer arrays.
     * @return: Their smallest difference.
     */
    public int smallestDifference(int[] A, int[] B) {
        // write your code here
        if(A == null || A.length == 0 || B == null || B.length == 0){
            return 0;
        }

        Arrays.sort(A);
        Arrays.sort(B);

        int a = 0; int b = 0;
        int min = Integer.MAX_VALUE;
        while(a < A.length && b < B.length){
            min = Math.min(min, Math.abs(A[a] - B[b]));
            if(A[a] < B[b]){
                a++;
            }else{
                b++;
            }
        }
        return min;
    }
}