gold-16-6

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

示例：

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)

提示：

• 1 <= a.length, b.length <= 100000
• -2147483648 <= a[i], b[i] <= 2147483647
• 正确结果在区间 [0, 2147483647] 内

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(b);
        int minDif = Integer.MAX_VALUE;

        for (int aa : a) {
            int df = getMinDif(aa, b);
            if (df >= 0 && df < minDif) {
                minDif = df;
            }
        }

        return minDif;
    }


    private int getMinDif(int v, int[] b) {
        int start = 0;
        int end = b.length - 1;

        while (start <= end) {
            if (start == end) {
                return getDif(v, b[start]);
            }
            if (start + 1 == end) {
                int v1 = getDif(v, b[start]);
                int v2 = getDif(v, b[end]);
                return Math.min(v1, v2);
            }
            if (start + 2 == end) {
                int v1 = getDif(v, b[start]);
                int v2 = getDif(v, b[start + 1]);
                int v3 = getDif(v, b[end]);
                return Math.min(v1, Math.min(v2, v3));
            }

            int mid = start + (end - start)/2;
            if (b[mid] == v) {
                return 0;
            } else if (b[mid] < v) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return -1;
    }

    private int getDif(int a, int b) {
        if (a > b) {
            return a - b;
        } else {
            return b - a;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)