GFG数组第K小元素题超时，大顶堆解法如何优化？

你的大顶堆思路本身没问题，超时主要是因为没有利用题目给出的有效范围参数l和r，导致遍历了整个数组（包括超出l到r的无关元素），浪费了不必要的时间。另外，针对极端大测试用例，还可以用更高效的快速选择算法进一步优化。

一、修复大顶堆解法的核心问题 #

题目中l和r是数组的有效索引范围（元素从a[l]到a[r]），你之前的代码遍历了a.length，会处理很多不属于测试范围的元素，这是超时的主要原因。修改后代码如下：

class Solution{
public static int kthSmallest(int[] a, int l, int r, int k) 
{ 
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    
    // 仅处理有效范围内的前k个元素
    for(int i = l; i < l + k && i <= r; i++) {
        pq.add(a[i]);
    }
    
    // 遍历剩余有效元素，维护堆的大小为k
    for(int i = l + k; i <= r; i++) {
        if(pq.peek() > a[i]) {
            pq.poll();
            pq.add(a[i]);
        }
    }
    
    return pq.peek();
} 
}

这个修改后，应该能通过大部分之前超时的测试用例。

二、进阶优化：快速选择算法 #

如果测试用例规模极大（比如数组长度百万级），堆解法的O(n logk)时间复杂度可能还是不够。此时可以用快速选择算法，平均时间复杂度为O(n)，通过随机化pivot可以避免最坏情况的O(n²)，实际运行效率远高于堆解法。

实现代码如下：

class Solution{
public static int kthSmallest(int[] a, int l, int r, int k) 
{ 
    if(l <= r) {
        int pivotIdx = partition(a, l, r);
        // 计算当前pivot在有效范围内的排名（从1开始）
        int rank = pivotIdx - l + 1;
        
        if(rank == k) {
            return a[pivotIdx];
        } else if(rank > k) {
            // 目标在左分区
            return kthSmallest(a, l, pivotIdx - 1, k);
        } else {
            // 目标在右分区，调整k值
            return kthSmallest(a, pivotIdx + 1, r, k - rank);
        }
    }
    return -1; // 逻辑上不会执行到这里
}

// 快速排序的分区函数，返回pivot的最终索引
private static int partition(int[] a, int l, int r) {
    // 随机选择pivot，避免最坏情况
    int randomIdx = l + (int)(Math.random() * (r - l + 1));
    swap(a, randomIdx, r);
    
    int pivot = a[r];
    int i = l - 1;
    
    for(int j = l; j < r; j++) {
        if(a[j] <= pivot) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
}

这个版本通过随机化pivot，几乎不会触发最坏情况，在大规模数据下的表现远超堆解法。

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