题目描述

给定两个整数数组 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] 内

题目思考

针对数组 a 的每个数字, 如何快速找到数组 b 和它绝对值差最小的数字?

解决方案

思路

分析题目, 一个很容易想到的思路就是暴力法, 二重循环统计每组数字对的绝对值差, 然后取最小值
但这种方法效率很低, 复杂度达到了 O(N^2), 有没有更高效的方法呢?
我们可以换个角度, 尝试直接定位绝对值差最小的数字:
1. 首先循环遍历数组 a 的每个数字 x
2. 然后在数组 b 里查找最接近 x 的两个数字(一大一小), 它们和 x 的绝对值差一定是最小的两个
3. 最后从所有这些绝对值差中取最小值, 即为最终结果
这里我们就可以使用二分查找的思路, 先对数组 b 排序, 然后查找它里面最接近且大于 x 的下标 j, 然后 j-1 下标一定是最接近且小于等于 x 的值, 只需统计这两个绝对值差即可
具体实现方面我们可以有以下三个优化:
1. 首先可以将两个数组去重, 没有必要重复计算相同数字
2. 其次可以比较去重后的长度, 然后选择排序较短的那个. 这样总体时间复杂度就是 O(SlogS+LlogS)=O(LlogS) (S 是较短数组的长度, L 是较长数组的长度), 而排序较长的数组的复杂度是 O(LlogL+SlogL)=O(LlogL), 效率稍微降低了一些
3. 最后可以在绝对值差存在 0 的时候直接返回, 因为不可能有更小的
下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解

复杂度

时间复杂度 O(LlogS): 参考上面的分析
空间复杂度 O(L+S): 使用集合去重, 如果不使用该优化的话则是 O(1)

代码

class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        # 排序后二分+三优化
        # 优化1 - 去重
        a = list(set(a))
        b = list(set(b))
        if len(a) < len(b):
            # 优化2 - 排序较短的数组
            return self.smallestDifference(b, a)
        b.sort()
        res = float("inf")
        for x in a:
            # 注意这里使用bisect, 这样查找到的j是首个大于x的下标, 只需要判断j-1和j即可
            j = bisect.bisect(b, x)
            for k in (j - 1, j):
                if 0 <= k < len(b):
                    res = min(res, abs(x - b[k]))
                    if res == 0:
                        # 优化3 - 差为0时直接返回, 不可能有更小的差
                        return res
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

[外链图片转存中...(img-fvFHdPbQ-1639201813810)]

程序员面试金典 - 面试题 16.06. 最小差

题目描述

示例：

提示：

题目思考

解决方案

思路

复杂度

代码