Easy

题目描述

给你个整数数组 arr，其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

  • a , b 均为数组 arr 中的元素
  • a < b
  • b - a 等于数组 arr 中任意两个元素的最小绝对差

示例 1：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
解释：最小绝对差是 1。符合条件的元素对有：
- [1,2]: |1 - 2| = 1
- [2,3]: |2 - 3| = 1
- [3,4]: |3 - 4| = 1

示例 2：

输入：arr = [1,3,6,10,15]
输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]

提示：

  • 2 <= arr.length <= 10^5
  • -10^6 <= arr[i] <= 10^6

解题思路

解题思路

这道题的核心思路是：对于已排序的数组，最小绝对差一定出现在相邻的两个元素之间。

算法步骤：

  1. 排序：首先对数组进行排序，这样相邻元素的差值就是局部最小的绝对差
  2. 找最小差值：遍历排序后的数组，找出所有相邻元素间的最小绝对差
  3. 收集结果：再次遍历数组，找出所有差值等于最小绝对差的相邻元素对

为什么最小绝对差一定在相邻元素间？

假设数组排序后为 a1 ≤ a2 ≤ a3 ≤ ... ≤ an，对于任意 i < j：

  • |ai - aj| = aj - ai（因为 ai ≤ aj）
  • 如果 j > i + 1，那么 aj - ai > aj - ai+1
  • 所以最小的绝对差一定出现在相邻元素之间

时间复杂度优化

虽然可以用 O(n²) 的暴力方法比较所有元素对，但通过排序后只比较相邻元素，我们可以将复杂度降低到 O(n log n)，其中排序占主要时间。

推荐解法：排序 + 两次遍历，时间复杂度最优，代码简洁易懂。

代码实现

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        
        int minDiff = INT_MAX;
        // 找到最小绝对差
        for (int i = 1; i < arr.size(); i++) {
            minDiff = min(minDiff, arr[i] - arr[i-1]);
        }
        
        vector<vector<int>> result;
        // 收集所有具有最小绝对差的元素对
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] - arr[i-1] == minDiff) {
                result.push_back({arr[i-1], arr[i]});
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        
        # 找到最小绝对差
        min_diff = min(arr[i] - arr[i-1] for i in range(1, len(arr)))
        
        # 收集所有具有最小绝对差的元素对
        result = []
        for i in range(1, len(arr)):
            if arr[i] - arr[i-1] == min_diff:
                result.append([arr[i-1], arr[i]])
        
        return result

public class Solution {
    public IList<IList<int>> MinimumAbsDifference(int[] arr) {
        Array.Sort(arr);
        
        int minDiff = int.MaxValue;
        // 找到最小绝对差
        for (int i = 1; i < arr.Length; i++) {
            minDiff = Math.Min(minDiff, arr[i] - arr[i-1]);
        }
        
        var result = new List<IList<int>>();
        // 收集所有具有最小绝对差的元素对
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] - arr[i-1] == minDiff) {
                result.Add(new List<int> { arr[i-1], arr[i] });
            }
        }
        
        return result;
    }
}

var minimumAbsDifference = function(arr) {
    arr.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    // 找到最小绝对差
    for (let i = 1; i < arr.length; i++) {
        minDiff = Math.min(minDiff, arr[i] - arr[i-1]);
    }
    
    const result = [];
    // 收集所有具有最小绝对差的元素对
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] - arr[i-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，两次遍历需要 O(n)
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目