本文介绍一种基于双优先队列（堆）的高效方法，在不显式删除原数组重复元素的前提下，准确获取去重后的第 k 小和第 k 大元素，时间复杂度为 o(n log k)，优于全排序方案。
本文介绍一种基于双优先队列（堆）的高效方法，在不显式删除原数组重复元素的前提下，准确获取去重后的第 k 小和第 k 大元素，时间复杂度为 o(n log k)，优于全排序方案。
在实际开发中，常需从整型数组中提取“第 k 小”和“第 k 大”的值。但需特别注意：若数组含重复元素（如 [5, 1, 8, 5, 9, 8, 0]），直接排序取索引 arr[k-1] 和 arr[n-k] 会将重复值计入顺序位置，导致结果错误——例如 k=3 时，全排序后为 [0,1,5,5,8,8,9]，第 3 小是 5（索引 2），第 3 大是 5（倒序第 3 个，即索引 4），而非 8。问题本质在于：k-th 应基于去重后的有序序列定义，而非原始数组的重复排序序列。
一种直观思路是先用 TreeSet 去重并排序，再转为数组访问。但该方法时间复杂度为 O(n log n)，且额外占用 O(n) 空间。更优解是使用双堆 + 哈希集合（HashSet） 的在线算法：
- 使用 最大堆（
PriorityQueue配Comparator.reverseOrder()） 维护当前遇到的 k 个最大不重复值，堆顶即为第 k 大； - 使用 最小堆（默认
PriorityQueue<integer></integer>） 维护当前遇到的 k 个最小不重复值，堆顶即为第 k 小； - 用
HashSet实时记录已处理过的数值，跳过重复项，确保每个值仅参与一次堆操作； - 遍历数组时：首次遇到某值 → 加入两堆；若堆已满（大小达 k），后续更优值（对最大堆是更小的数，对最小堆是更大的数）才触发替换。
以下是完整、可运行的实现：
import java.util.*;
public class KthSmallestAndLargestArray {
static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
static int[] findKthSmallestAndLargest(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0 || k > new HashSet<>(Arrays.stream(arr).boxed().toList()).size()) {
throw new IllegalArgumentException("Invalid k: must be between 1 and number of unique elements");
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // for k smallest
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // for k largest
Set<Integer> seen = new HashSet<>();
for (int value : arr) {
if (!seen.add(value)) continue; // skip duplicates
if (minHeap.size() < k) {
minHeap.offer(value);
maxHeap.offer(value);
} else {
// For maxHeap (k largest): keep only top-k, so replace if current < top
if (value < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(value);
}
// For minHeap (k smallest): keep only top-k, so replace if current > top
if (value > minHeap.peek()) {
minHeap.poll();
minHeap.offer(value);
}
}
}
return new int[]{maxHeap.peek(), minHeap.peek()}; // {k-th largest, k-th smallest}
}
public static void main(String[] args) {
int[] arr = {5, 1, 8, 5, 9, 8, 0};
int k = 3;
System.out.println("Original Array:");
printArray(arr);
int[] result = findKthSmallestAndLargest(arr, k);
System.out.printf("For k = %d: %d-th largest = %d, %d-th smallest = %d%n",
k, k, result[0], k, result[1]); // Output: 5-th largest = 5, 3-th smallest = 5
}
}✅ 关键优势：
立即学习“Java免费学习笔记（深入）”；
-
时间效率高：O(n log k)，远优于
Arrays.sort()的 O(n log n)； - 空间可控：仅需 O(k) 堆空间 + O(u) 哈希集（u 为唯一元素数）；
- 逻辑清晰：分离“去重”与“选 top-k”两个关注点，避免修改原数组。
⚠️ 注意事项：
- 输入校验必不可少：k 必须 ≤ 唯一元素总数，否则无解；
- 堆初始化必须严格控制大小（始终 ≤ k），否则无法保证堆顶为第 k 位；
- 不要混淆返回顺序：示例中
result[0]是第 k 大，result[1]是第 k 小； - 若需求允许重复计数（即按原始排序位置取值），则应改用快速选择（QuickSelect）或直接排序——但本题明确要求“去重后第 k 位”，双堆法是最贴切解法。
总结：当面对“k-th 最值 + 去重”组合需求时，双优先队列是兼顾效率、可读性与健壮性的首选方案。
