本文介绍在不显式删除重复元素的前提下，使用优先队列（堆）与哈希集合协同实现 O(n log k) 时间复杂度的解决方案，准确返回第 k 小和第 k 大的唯一值（如对 [5,1,8,5,9,8,0] 求 k=3，结果为 5 和 5）。
本文介绍在不显式删除重复元素的前提下，使用优先队列（堆）与哈希集合协同实现 o(n log k) 时间复杂度的解决方案，准确返回第 k 小和第 k 大的**唯一值**（如对 [5,1,8,5,9,8,0] 求 k=3，结果为 5 和 5）。
在实际开发中，频繁遇到“求第 k 大/小元素”需求，但若直接排序后取索引（如 arr[k-1] 和 arr[n-k]），会因重复值导致逻辑错误——例如数组 [5, 1, 8, 5, 9, 8, 0] 排序后为 [0,1,5,5,8,8,9]，取第 3 小（索引 2）和第 3 大（索引 4）得 5 和 8，但按去重后的有序序列 [0,1,5,8,9]，第 3 小与第 3 大均为 5。问题本质在于：k 指的是第 k 个不同（distinct）值的位置，而非原始数组中的第 k 个索引。
为兼顾效率与语义准确性，推荐采用双堆 + 哈希去重策略：
- 使用 最大堆（Max-Heap） 维护当前遇到的
k个最大不重复值，堆顶即为第 k 大； - 使用 最小堆（Min-Heap） 维护当前遇到的
k个最小不重复值，堆顶即为第 k 小； - 用
HashSet<integer></integer>实时记录已处理过的数值，跳过重复项，确保每个值仅参与一次堆操作； - 遍历数组时动态调整堆大小：前
k个新值直接入堆；后续值仅当优于堆顶时才替换（例如新值比最大堆顶更小，则替换以保留更大的候选集）。
以下是完整可运行示例：
import java.util.*;
public class KthSmallestAndLargestArray {
static void printArray(int[] arr) {
for (int i = 0; i Arrays.stream(arr).boxed()
.collect(Collectors.toSet()).size()) {
throw new IllegalArgumentException("Invalid k or empty array");
}
PriorityQueue<integer> minHeap = new PriorityQueue(); // for k smallest
PriorityQueue<integer> maxHeap = new PriorityQueue(Collections.reverseOrder()); // for k largest
Set<integer> seen = new HashSet();
for (int value : arr) {
if (!seen.add(value)) continue; // skip duplicates
if (minHeap.size() minHeap.peek()
if (value > minHeap.peek()) {
minHeap.poll();
minHeap.offer(value);
}
// Maintain top-k largest: replace if current <p>✅ <strong>关键优势</strong>： </p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java"><img
src="https://img.php.cn/upload/skill/000/000/081/178955835420587.jpg" alt="Alibabacloud Sdk Client Initialization For Java" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="overflowclass">Alibabacloud Sdk Client Initialization For Java</a>
<p class="overflowclass">在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。</p>
</div>
<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>时间复杂度 <strong>O(n log k)</strong>，显著优于全排序的 O(n log n)，尤其当 k ≪ n 时； </li>
<li>空间复杂度 <strong>O(k)</strong>，仅需存储最多 2k 个元素及哈希集； </li>
<li>语义严谨：自动跳过重复值，严格按 distinct 排序序列定位。</li>
</ul>
<p>⚠️ <strong>注意事项</strong>： </p>
<ul>
<li>若输入 <code>k</code> 超出不重复元素总数（如 <code>k=10</code> 但数组只有 5 个不同值），应提前校验并抛出异常； </li>
<li>堆初始化时务必使用 <code>Collections.reverseOrder()</code> 构建最大堆，避免误用自然序； </li>
<li>
<code>seen.add(value)</code> 返回 <code>true</code> 表示首次遇到该值，是去重逻辑的核心判断依据。</li>
</ul>
<p>该方案平衡了性能、可读性与业务准确性，适用于高频查询、流式数据或内存受限场景，是解决“第 k 个不重复极值”问题的标准实践。</p></integer></integer></integer>Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
