最小差

给定两个整数数组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
正确结果在区间[-2147483648, 2147483647]内
通过次数7,396提交次数17,910

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-difference-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

先对两个数组排序，然后以做两个有序链表合并成一个有序链表的思路，计算相邻的两个来自不同数组的元素的差值，并记录最小值

class Solution {
    public int smallestDifference(int[] a, int[] b) {
        if (a == null && b == null) return 0;
        if (a.length == 0 || b.length == 0) return 0;
        Arrays.sort(a);
        Arrays.sort(b);
        int indexA = 0, indexB = 0;
        int lastAValue = 0;
        int lastBValue = 0;
        long min = (long)Integer.MAX_VALUE;
        char last = '0';

        while (indexA < a.length || indexB < b.length) {
            if (indexA < a.length && indexB < b.length) {
                if (a[indexA] < b[indexB]) {
                    lastAValue = a[indexA];
                    if (last == 'b') {
                        min = Math.min(Math.abs((long)a[indexA] - (long)lastBValue), min);
                    }
                    last = 'a';
                    indexA++;
                } else if (a[indexA] > b[indexB]) {
                    lastBValue = b[indexB];
                    if (last == 'a') {
                        min = Math.min(Math.abs((long)b[indexB] - (long)lastAValue), min);
                    }
                    last = 'b';
                    indexB++;
                } else {
                    return 0;
                }
            } else if (indexA < a.length && Math.abs((long)a[indexA] - (long)lastBValue) <= min) {
                return (int) Math.abs((long)a[indexA] - (long)lastBValue);
            } else if (indexB < b.length && Math.abs((long)b[indexB] - (long)lastAValue) <= min) {
                return (int) Math.abs((long)b[indexB] - (long)lastAValue);
            } else {
                break;
            }
        }
        return (int)min;
    }
}

更优雅的写法

class Solution {
    public int smallestDifference(int[] a, int[] b) {
        if (a == null || b == null || a.length == 0 || b.length == 0) return -1;
        int minDiff = Integer.MIN_VALUE , aIdx = 0 , bIdx = 0;
        Arrays.sort(a);
        Arrays.sort(b);
        while (aIdx < a.length && bIdx < b.length) {
            //关键，解决溢出 ， 负数域 大于 正数域。
            minDiff = Math.max(minDiff,-Math.abs(a[aIdx] - b[bIdx]));

            if (a[aIdx] < b[bIdx]) {
                aIdx++;
            }
            else {
                bIdx++;
            }
        }
        //反置
        return Math.abs(minDiff);
    }
}

作者：tago-tech
链接：https://leetcode-cn.com/problems/smallest-difference-lcci/solution/shuang-zhi-zhen-jie-jue-absyi-chu-fang-fa-by-lcbir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：tago-tech来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信