LeetCode 面试题 16.06. 最小差
题目描述
题意分析
从数组
a中选一个数，再从数组b中选一个数，使两数的绝对差最小，返回这个差值。两个数必须分别来自两个数组，不能改成在同一个数组内部寻找相邻差。数组不保证有序，可以包含负数和重复值；两边存在相同值时，最小差就是零。任意一对数的差可能超过 32 位整数范围，但题目保证最终的最小差能放入返回类型，因此计算过程仍需使用宽整数。
解法：排序 + 双指针
核心思路
[!blue]
如果直接枚举所有跨数组配对，需要比较两个数组长度的乘积那么多次。先分别升序排序，再让两个指针从最小元素开始比较，就能利用顺序排除一整批不可能更优的配对。
每轮先用当前两项更新最小差。若
a[i] < b[j]，固定a[i]再配上b中更靠后的元素，只会让差距更大或相同，不能优于刚比较过的这一对。因此a[i]已经没有继续保留的必要，移动i。反过来，若a[i] > b[j]，同理移动j。已经越过的候选，在被移出时也经过了同样的排除判断，所以不必回头比较。每次只淘汰较小一侧，就能在不漏掉更优配对的前提下逐步缩小剩余范围；任一数组耗尽后，其他未比较配对都无法改善已有结果。
若当前两项相同，差值已经达到理论下界零，可以立即结束。减法必须先把两个操作数转成 64 位，再相减并取绝对值；在窄整数里溢出后再转换，已经无法恢复真实差值。
这份实现直接排序两个输入数组，因此会改变它们原来的顺序，但不会改变可选数值及最小差。
解题步骤
- 分别将两个数组升序排序，令
i = j = 0，用足够大的宽整数初始化答案。- 两指针都未越界时，把当前元素提升为 64 位，计算绝对差并更新答案。
- 差值为零时直接返回；否则只移动数值较小的一侧指针。
- 任一数组扫描完成后，按题目保证将最终最小差转换为返回类型。
代码实现
class Solution {
public int smallestDifference(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);
int i = 0;
int j = 0;
long answer = Long.MAX_VALUE;
while (i < a.length && j < b.length) {
// 在减法之前提升宽度，避免极值之差先在窄整数内溢出
long first = a[i];
long second = b[j];
answer = Math.min(answer, Math.abs(first - second));
if (answer == 0) {
return 0;
}
// 较小值配更大的后续对手不会改善差距，排除较小侧
if (first < second) {
i++;
} else {
j++;
}
}
return (int) answer;
}
}
import "sort"
func smallestDifference(a, b []int) int {
sort.Ints(a)
sort.Ints(b)
i, j := 0, 0
answer := int64(1 << 62)
for i < len(a) && j < len(b) {
// 在减法之前提升宽度，避免极值之差先在窄整数内溢出
first, second := int64(a[i]), int64(b[j])
diff := first - second
if diff < 0 {
diff = -diff
}
if diff < answer {
answer = diff
}
if answer == 0 {
return 0
}
// 较小值配更大的后续对手不会改善差距，排除较小侧
if first < second {
i++
} else {
j++
}
}
return int(answer)
}
复杂度分析
设两个数组长度分别为 $m$、$n$。
- 时间复杂度：$O(m\log(m+1)+n\log(n+1))$，包含排序；排序后的双指针扫描只需 $O(m+n)$。
- 辅助空间复杂度：双指针部分为 $O(1)$，整体辅助空间取决于标准库排序实现。
关键点总结
[!green]
- 移动较小值，因为它与更大的后续对手不可能形成更小差距。
- 差值为零即可结束，绝对差不会再小。
- 宽整数转换发生在减法之前，排序则直接作用于输入数组。
易错点总结
[!yellow]
- 每轮同时移动两个指针，会跳过仍可能改善答案的交叉配对。
- 在两个指针移动之前先计算当前差，不能把当前这一对直接略过。
- 在 32 位内相减后才转成 64 位，无法修复已经发生的溢出。
- 对窄类型的最小负数直接取绝对值也可能仍为负，应先使用宽类型保存差值。
- 题目只返回最小差，不必为了输出一对数或恢复原始下标增加额外结构。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1200. 最小绝对差 | 简单 | 原题在一个数组中比较排序相邻值，本题必须从两个不同数组各取一个，双指针更直接。 |
| 658. 找到 K 个最接近的元素 | 中等 | 同样依靠有序性寻找最近值，本题只求跨两数组的最小差，不返回k个邻近元素。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！