# 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

```java
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;
    }
}
```