The Smallest Difference

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

Tags

Two Pointers LintCode Copyright Sort Array

Analysis

Brutal Force 双重for循环，找Math.abs(A[i] - B[j])的最小值

先排序 O(nlogn) 之后也有两种思路：

1. 再通过二分查找O(logn)，在B[j]中找接近A[i]的元素，找n次，总共时间复杂度O(n * logn)

2. two pointers，只要A[i] < B[j]，那么i++；反之，j++，循环结束条件就是i, j有一者达到数组边界

例如题目中的示例：

A = [3,6,7,4]
B = [2,8,9,3]

排序后：

A = [3,4,6,7]
B = [2,3,8,9]

排过序后，当A[i] < B[j]时，A[]中更接近B[j]的则可能出现在A[i]其后，因此i++；反过来，则需要j++

另：想起了牛顿法中寻找f(x) = 0，零点存在于f(x1) < 0, f(x2) > 0这个区间。在本题中，则是A[i1] < B[j], 那么如果有A[i2] > B[j]，则中间有可能就有这样的“零点”，也就是A[i]与B[j]差值的绝对值为零的情况。

Solution

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

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

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