程序员面试金典面试题16。06。最小差

　　题目难度: 中等
　　原题链接  [1]
　　今天继续更新程序员面试金典系列, 大家在公众号   算法精选   里回复  面试金典   就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
　　给定两个整数数组 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), 有没有更高效的方法呢? 我们可以换个角度, 尝试直接定位绝对值差最小的数字:  首先循环遍历数组 a 的每个数字 x 然后在数组 b 里查找最接近 x 的两个数字(一大一小), 它们和 x 的绝对值差一定是最小的两个 最后从所有这些绝对值差中取最小值, 即为最终结果 这里我们就可以使用二分查找的思路, 先对数组 b 排序, 然后查找它里面最接近且大于 x 的下标 j, 然后 j-1 下标一定是最接近且小于等于 x 的值, 只需统计这两个绝对值差即可 具体实现方面我们可以有以下三个优化:  首先可以将两个数组去重, 没有必要重复计算相同数字 其次可以比较去重后的长度, 然后选择排序较短的那个. 这样总体时间复杂度就是 O(SlogS+LlogS)=O(LlogS) (S 是较短数组的长度, L 是较长数组的长度), 而排序较长的数组的复杂度是 O(LlogL+SlogL)=O(LlogL), 效率稍微降低了一些 最后可以在绝对值差存在 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 参考资料
　　[1]
　　原题链接: https://leetcode-cn.com/problems/smallest-difference-lcci/