如何优化寻找数组最小k个元素对绝对差值的算法时间复杂度

问题背景 #

给定数值数组3,1,3,5与整数k=3，需求为找出数组中元素对的绝对差值最小的k个值。所有可能的元素对差值如下：

|3 - 1| = 2
|3 - 3| = 0
|3 - 5| = 2
|1 - 3| = 2
|1 - 5| = 4
|3 - 5| = 2

预期结果为最小的3个差值：[0,2,2]

原实现方法通过枚举所有元素对并排序取前k个值，时间复杂度为O(n² log n)，当数组规模较大时效率极低，以下是优化方案：

优化思路 #

数组排序后，最小的差值必然出现在相邻或间隔较小的元素对之间。利用**最小堆（优先队列）**可以避免枚举所有元素对，仅维护候选的最小差值集合，逐步提取前k个最小值：

1. 先对数组排序，时间复杂度O(n log n)
2. 初始化最小堆，存入所有相邻元素的差值及对应索引（差值, 左索引, 右索引）
3. 循环k次：
   • 取出堆顶的最小差值，加入结果列表
   • 将当前左索引与右索引+1的差值（若右索引+1未越界）加入堆，确保后续能找到次小的候选差值
4. 整体时间复杂度优化为O(n log n + k log n)，当k远小于n²时，效率提升显著

优化后的Java实现 #

import java.util.*;

public class MinDiffPairs {
    public static List<Integer> process(List<Integer> list, int k) {
        Collections.sort(list);
        int n = list.size();
        List<Integer> result = new ArrayList<>();
        
        // 最小堆：存储三元组(差值, 左索引, 右索引)，按差值升序排列
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        
        // 初始化堆，加入所有相邻元素对的差值
        for (int i = 0; i < n - 1; i++) {
            int diff = list.get(i + 1) - list.get(i);
            minHeap.offer(new int[]{diff, i, i + 1});
        }
        
        // 提取前k个最小差值
        while (k > 0 && !minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int diff = current[0];
            int i = current[1];
            int j = current[2];
            
            result.add(diff);
            k--;
            
            // 如果右索引还能右移，加入新的候选差值
            if (j + 1 < n) {
                int newDiff = list.get(j + 1) - list.get(i);
                minHeap.offer(new int[]{newDiff, i, j + 1});
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(3, 1, 3, 5);
        System.out.println(process(list, 3)); // 输出 [0,2,2]
    }
}

关键说明 #

• 排序后，元素对的差值无需计算绝对值，因为list.get(j) - list.get(i)必然非负
• 堆中存储索引而非具体数值，避免重复计算差值，同时能快速定位下一个候选元素对
• 该方法不会遗漏任何可能的最小差值：排序后，对于索引i，最小的差值依次是i与i+1、i与i+2...的差值，通过堆的优先级保证每次取出当前最小的差值

内容的提问来源于stack exchange，提问作者Learner