如何在 Java 中高效获取数组中第 k 大与第 k 小的元素（去重后）-java教程-PHP中文网

如何在 Java 中高效获取数组中第 k 大与第 k 小的元素（去重后）

本文介绍一种基于双优先队列（堆）的高效方法，在不显式删除原数组重复元素的前提下，准确获取去重后的第 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  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()  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
    }
}</integer></integer></integer>

✅ 关键优势：