SYSTEM
算法笔记:哈希表 + 堆(TopK专项)
src/content/notes/algorithm/哈希表-堆专项.md 格式对齐之前二分、滑动窗口、单调栈笔记:题目信息 → 题意简述 → 核心思路 → 手动模拟 → Java完整代码 → 通用模板 → 复杂度 → 总结&易错点 包含题目: LC49 字母异位词分组、LC128 最长连续序列、LC215 数组中的第K个最大元素、LC347 前K个高频元素、LC973 最接近原点的K个点 TopK两种解法:堆(PriorityQueue)、快速选择quickselect
前置知识
HashMap常用刷题方法
| 方法 | 作用 |
|---|---|
map.getOrDefault(key,0) |
key不存在返回默认值,存在返回value |
map.computeIfAbsent(key,k‑>new ArrayList<>()) |
key不存在则新建对象,返回value引用 |
map.entrySet() |
获取key‑value键值对集合 |
PriorityQueue(优先队列‑堆)
// 默认:小顶堆,堆顶最小
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 大顶堆写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->b‑a);
offer():入堆;poll():弹出堆顶;peek():查看堆顶不删除- ✅求前K大 → 小顶堆,维持堆大小k,超过k弹出堆顶最小值
- ✅求前K小 → 大顶堆,维持堆大小k,超过k弹出堆顶最大值
TopK口诀:保留k个,淘汰最差的,堆内就是答案
例题1 LC49 字母异位词分组
题目信息:给字符串数组,将字母异位词组合在一起,异位词:字母以及每个字母数量相同,顺序不同。 示例:strs = ["eat","tea","tan","ate","nat","bat"] 输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
题意简述
把字符组成完全一样的字符串分到同一组。
核心思路
- 字母异位词排序后的字符串一定相等,把排序后的字符串作为HashMap的key。
- value保存属于该组的原始字符串List。
- 遍历全部字符串,生成key,加入对应List;最后收集map所有value返回。
手动模拟
输入["eat","tea","tan","ate","nat","bat"]
- “eat”排序→“aet”,map新建key=“aet”,list存入”eat”
- “tea”排序→“aet”,追加到list;map
{"aet":["eat","tea"]} - “tan”排序→“ant”新建分组;“ate”排序→“aet”追加;“nat”→“ant”追加;“bat”→“abt”新建分组
- 取出全部value得到结果。
完整代码
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String s : strs){
char[] ch = s.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
}
模板
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String s : strs){
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.computeIfAbsent(key, k->new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
复杂度
- 时间:$O(nk\log k)$,n字符串数量,k字符串最大长度,每个字符串排序$O(k\log k)$
- 空间:$(O(nk))$
总结&易错点
- key必须是排序后的字符串,不能用原字符串。
computeIfAbsent简化if‑contains判断。- 进阶:可以用
int[26]字符计数数组转字符串做key,时间$(O(nk))$,不需要排序。
例题2 LC128 最长连续序列
题目信息:未排序整数数组,找出数字连续最长序列的长度;要求时间复杂度O(n)。 示例:nums = [100,4,200,1,3,2],输出4,序列1,2,3,4
题意简述
不要求原数组下标连续,只看数值是否连续递增;不能排序(排序$O(n\log n)$不满足要求)。
核心思路
- HashSet存入全部数字,自动去重,O(1)查询。
- 遍历set中的数字x:只有`x‑1不在集合中,x才是一段连续序列起点。
- 从起点向后不断查找
x+1,x+2...统计长度;跳过非起点元素保证整体O(n)。
手动模拟
set={100,4,200,1,3,2}
- x=100,99不在集合,起点;向后无,len=1
- x=4,3存在,不是起点,跳过
- x=200,199不在,len=1
- x=1,0不在集合,起点;向后找到2,3,4,len=4
- x=2、x=3,x‑1存在,直接跳过。max=4。
完整代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums) set.add(num);
int maxLen = 0;
for(int x : set){
if(!set.contains(x‑1)){
int cur = x;
int len = 1;
while(set.contains(cur + 1)){
cur++;
len++;
}
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
}
模板
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums) set.add(num);
int maxLen = 0;
for(int x : set){
if(!set.contains(x‑1)){
int cur = x;
int len = 1;
while(set.contains(cur+1)){ cur++; len++; }
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
复杂度
- 时间:O(n);每个元素最多访问两次
- 空间:O(n),HashSet存储元素
总结&易错点
- 遍历set而不是原nums数组,规避重复数字重复计算。
!set.contains(x‑1)是核心,去掉该条件会退化O(n²)超时。- 空数组直接返回0,代码天然兼容。
例题3 LC215 数组中的第K个最大元素
题目信息:返回数组第k个最大元素,不是第k个不同元素。 示例:nums=[3,2,1,5,6,4],k=2,输出5。
题意简述
排序后从大到小数第k个。
解法A:小顶堆解法(面试优先写,不修改原数组)
核心思路
维护大小为k的小顶堆;遍历所有数字入堆,堆超过k则弹出堆顶最小值。遍历结束堆顶就是第k大。
手动模拟 nums=[3,2,1,5,6,4],k=2
- 3入堆;2入堆,size=2
- 1入堆,size>2,poll弹出1;堆[2,3]
- 5入堆 size>2,poll弹出2;堆[3,5]
- 6入堆 size>2,poll弹出3;堆[5,6]
- 4入堆 size>2,poll弹出4;堆[5,6];peek得到5。
完整代码
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums){
minHeap.offer(num);
if(minHeap.size()>k){
minHeap.poll();
}
}
return minHeap.peek();
}
}
解法B:快速选择 quickselect(平均O(n),原地修改数组)
复用快排partition;目标下标
target = nums.length‑k,找到该下标直接返回。
class Solution {
public int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length‑1;
int target = nums.length‑k;
while(true){
int pivot = partition(nums,left,right);
if(pivot == target) return nums[pivot];
else if(pivot < target) left = pivot+1;
else right = pivot‑1;
}
}
private int partition(int[] nums,int l,int r){
int pivotVal = nums[r];
int i=l;
for(int j=l;j<r;j++){
if(nums[j] < pivotVal){
swap(nums,i,j);
i++;
}
}
swap(nums,i,r);
return i;
}
void swap(int[] arr,int a,int b){
int t=arr[a];arr[a]=arr[b];arr[b]=t;
}
}
模板(堆求第K大)
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums){
minHeap.offer(num);
if(minHeap.size()>k) minHeap.poll();
}
return minHeap.peek();
}
复杂度
- 堆解法:时间$O(n\log k)$,空间$(O(k))$
- 快速选择:平均O(n),最坏O(n²);空间O(1)原地。
总结&易错点
- PriorityQueue默认小顶堆。
- 快速选择目标下标是
n‑k,不要直接用k。 - 快速选择修改原数组;不允许修改输入优先堆解法。
例题4 LC347 前K个高频元素
题目信息:返回数组出现频率前k高的元素。 示例:nums=[1,1,1,2,2,3],k=2,输出[1,2]
题意简述
按出现频次做TopK。
核心思路
- HashMap统计每个数字出现频次。
- 小顶堆存
Map.Entry,比较频率value;维持堆大小k,超过k弹出频率最小。 - 遍历哈希表全部entry;最后取出堆内key返回。
手动模拟
map统计{1:3,2:2,3:1},k=2
- entry(1,3)入堆;entry(2,2)入堆 size=2
- entry(3,1)入堆 size>2,poll弹出(3,1);堆保留(2,2),(1,3)
- 取出key得到
[2,1],题目不要求顺序。
完整代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> freqMap = new HashMap<>();
for(int num : nums){
freqMap.put(num, freqMap.getOrDefault(num,0)+1);
}
//小顶堆,按频率升序
PriorityQueue<Map.Entry<Integer,Integer>> minHeap =
new PriorityQueue<>((a,b)‑>a.getValue()‑b.getValue());
for(var entry : freqMap.entrySet()){
minHeap.offer(entry);
if(minHeap.size()>k) minHeap.poll();
}
int[] res = new int[k];
int idx=0;
while(!minHeap.isEmpty()){
res[idx++] = minHeap.poll().getKey();
}
return res;
}
}
模板
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums) map.put(num,map.getOrDefault(num,0)+1);
PriorityQueue<Map.Entry<Integer,Integer>> heap =
new PriorityQueue<>((x,y)‑>x.getValue()‑y.getValue());
for(var entry : map.entrySet()){
heap.offer(entry);
if(heap.size()>k) heap.poll();
}
int[] ans=new int[k];
int i=0;
while(!heap.isEmpty()) ans[i++] = heap.poll().getKey();
return ans;
}
复杂度
- 时间:O(n\log k);空间O(n)哈希表。
总结&易错点
- 堆比较频率value,不是key。
- 使用小顶堆,只保存k个,效率优于全部入堆大顶堆。
例题5 LC973 最接近原点的K个点
题目信息:二维平面点,返回距离原点最近k个点;距离平方 $x^2+y^2$,不用开根号。 示例:points=[[1,3],[-2,2]],k=1,输出[[-2,2]]
解法A:堆解法(大顶堆,保留前k小距离)
核心思路
求前k小距离,使用大顶堆,堆内存k个点,堆顶是堆内距离最大;超过k就弹出堆顶。遍历结束堆内即为最近k个点。
完整代码
class Solution {
public int[][] kClosest(int[][] points, int k) {
//大顶堆:距离大的在堆顶
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)‑>{
long da = (long)a[0]*a[0] + (long)a[1]*a[1];
long db = (long)b[0]*b[0] + (long)b[1]*b[1];
return Long.compare(db, da);
});
for(int[] p : points){
maxHeap.offer(p);
if(maxHeap.size()>k) maxHeap.poll();
}
int[][] res = new int[k][2];
for(int i=0;i<k;i++) res[i] = maxHeap.poll();
return res;
}
}
解法B:快速选择(随机pivot,平均O(n),修改原数组)
class Solution {
public int[][] kClosest(int[][] points, int k) {
int left = 0, right = points.length‑1;
while(left <= right){
int pivotIdx = partition(left,right,points);
if(pivotIdx == k‑1) break;
else if(pivotIdx < k‑1) left = pivotIdx+1;
else right = pivotIdx‑1;
}
return Arrays.copyOfRange(points,0,k);
}
private int partition(int left,int right,int[][] points){
int rand = new Random().nextInt(right‑left+1)+left;
swap(rand,right,points);
long pivotDist = dist(points[right]);
int i=left;
for(int j=left;j<right;j++){
if(dist(points[j]) <= pivotDist){
swap(i,j,points);
i++;
}
}
swap(i,right,points);
return i;
}
private long dist(int[] p){
long x=p[0],y=p[1];
return x*x+y*y;
}
private void swap(int i,int j,int[][] points){
int[] t=points[i]; points[i]=points[j]; points[j]=t;
}
}
模板(TopK通用伪代码)
// 求前K小 → 大顶堆,size>k就poll
// 求前K大 → 小顶堆,size>k就poll
PriorityQueue<T> heap = new PriorityQueue<>(比较器);
for(元素 : 数组){
heap.offer(元素);
if(heap.size()>k) heap.poll();
}
//堆内就是结果
复杂度
- 堆:O(n\log k),空间(O(k))
- 快速选择:平均O(n),原地修改数组
总结&易错点
- 距离计算要使用
long,防止int数值溢出。 - 前K小用大顶堆,不要搞反比较器。
📋哈希+堆TopK综合速查表
| 题号 | 题目 | 核心算法 | 堆类型 | 关键条件 |
|---|---|---|---|---|
| 49 | 字母异位词分组 | HashMap排序key | 无 | 排序字符串作为key分组 |
| 128 | 最长连续序列 | HashSet | 无 | 只从序列起点向后遍历 |
| 215 | 第K个最大元素 | TopK堆/快速选择 | 小顶堆 | 维护堆大小k,堆顶答案 |
| 347 | 前K高频元素 | HashMap+TopK堆 | 小顶堆 | 比较entry的frequency |
| 973 | 最接近原点K个点 | TopK堆/快速选择 | 大顶堆 | 比较距离平方,注意溢出 |
TopK通用两套方案对比
| 方案 | 时间 | 空间 | 特点 | 适用场景 |
|---|---|---|---|---|
| 堆解法 | $O(n\log k)$ | (O(k)) | 不修改原数组;适合海量数据,内存有限 | 笔试面试优先写 |
| 快速选择quickselect | 平均O(n),最坏O(n²) | O(1)原地 | 修改输入数组;随机pivot规避最坏情况 | 允许修改原数组场景 |
高频踩坑总览
- PriorityQueue默认是小顶堆,大顶堆必须传比较器。
- TopK:前K大用小顶堆;前K小用大顶堆,维持堆大小k。
- 数值平方计算注意int溢出,转long。
- 快速选择会修改原输入,如果业务不允许,不能使用。
- HashMap遍历
entrySet()拿键值对;HashSet用来去重+O(1)查询。
配套笔记:二分查找、滑动窗口、单调栈、二叉树BFS层序遍历、本份哈希+堆TopK专项。