1200. 最小绝对差
题目描述
输入整数数组 arr，其中元素两两不同。
先求出数组中任意两个元素之差的绝对值的最小值，记为 d。找出所有满足 a < b 且 b - a == d 的元素对 [a, b]。
返回这些元素对组成的列表，按升序排列（先比 a，再比 b）。
示例 1
输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]
解释：最小差为 1，相邻整数两两成对。
示例 2
输入：arr = [1,3,6,10,15] 输出：[[1,3]]
解释：最小差为 2，只有 1 和 3。
示例 3
输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
解释：最小差为 4，满足的有 [-14,-10]、[19,23]、[23,27]。
数据范围
2 <= arr.length <= 10^5-10^6 <= arr[i] <= 10^6
解题思路
排序后，差值最小的两个数一定相邻：如果 a < c < b，那么 b - a 一定大于 c - a。所以先排序，扫描一遍相邻差求出最小值 best，再扫描一遍把相邻差等于 best 的对按顺序收集起来，结果天然是升序的。
为什么正确
排序后，任何最小绝对差的数对都是相邻元素 (arr[i], arr[i+1])；按 i 从小到大收集，结果就是升序。
复杂度分析
时间 O(n log n)（排序），空间 O(1)（不计答案和排序栈）。
易错点
不必枚举所有 O(n^2) 个数对；也不要在第一遍里边求最小边收集时忘记在 best 变小时清空已收集的结果。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
arr.sort()
best = min(arr[i + 1] - arr[i] for i in range(len(arr) - 1))
res = []
for i in range(len(arr) - 1):
if arr[i + 1] - arr[i] == best:
res.append([arr[i], arr[i + 1]])
return resclass Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int best = Integer.MAX_VALUE;
for (int i = 0; i + 1 < arr.length; i++) best = Math.min(best, arr[i + 1] - arr[i]);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i + 1 < arr.length; i++) {
if (arr[i + 1] - arr[i] == best) {
res.add(Arrays.asList(arr[i], arr[i + 1]));
}
}
return res;
}
}class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
sort(arr.begin(), arr.end());
int best = INT_MAX;
for (int i = 0; i + 1 < (int)arr.size(); i++) best = min(best, arr[i + 1] - arr[i]);
vector<vector<int>> res;
for (int i = 0; i + 1 < (int)arr.size(); i++) {
if (arr[i + 1] - arr[i] == best) {
res.push_back({arr[i], arr[i + 1]});
}
}
return res;
}
};func minimumAbsDifference(arr []int) [][]int {
sort.Ints(arr)
best := math.MaxInt64
for i := 0; i+1 < len(arr); i++ {
best = min(best, arr[i+1]-arr[i])
}
res := [][]int{}
for i := 0; i+1 < len(arr); i++ {
if arr[i+1]-arr[i] == best {
res = append(res, []int{arr[i], arr[i+1]})
}
}
return res
}var minimumAbsDifference = function(arr) {
arr.sort((a, b) => a - b);
let best = Infinity;
for (let i = 0; i + 1 < arr.length; i++) best = Math.min(best, arr[i + 1] - arr[i]);
const res = [];
for (let i = 0; i + 1 < arr.length; i++) {
if (arr[i + 1] - arr[i] === best) {
res.push([arr[i], arr[i + 1]]);
}
}
return res;
};function minimumAbsDifference(arr: number[]): number[][] {
arr.sort((a, b) => a - b);
let best = Infinity;
for (let i = 0; i + 1 < arr.length; i++) best = Math.min(best, arr[i + 1] - arr[i]);
const res: number[][] = [];
for (let i = 0; i + 1 < arr.length; i++) {
if (arr[i + 1] - arr[i] === best) {
res.push([arr[i], arr[i + 1]]);
}
}
return res;
}