← 返回学习路线

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"]]

题意简述

把字符组成完全一样的字符串分到同一组。

核心思路

  1. 字母异位词排序后的字符串一定相等,把排序后的字符串作为HashMap的key。
  2. value保存属于该组的原始字符串List。
  3. 遍历全部字符串,生成key,加入对应List;最后收集map所有value返回。

手动模拟

输入["eat","tea","tan","ate","nat","bat"]

  1. “eat”排序→“aet”,map新建key=“aet”,list存入”eat”
  2. “tea”排序→“aet”,追加到list;map{"aet":["eat","tea"]}
  3. “tan”排序→“ant”新建分组;“ate”排序→“aet”追加;“nat”→“ant”追加;“bat”→“abt”新建分组
  4. 取出全部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))$

总结&易错点

  1. key必须是排序后的字符串,不能用原字符串。
  2. computeIfAbsent简化if‑contains判断。
  3. 进阶:可以用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)$不满足要求)。

核心思路

  1. HashSet存入全部数字,自动去重,O(1)查询。
  2. 遍历set中的数字x:只有`x‑1不在集合中,x才是一段连续序列起点。
  3. 从起点向后不断查找x+1,x+2...统计长度;跳过非起点元素保证整体O(n)。

手动模拟

set={100,4,200,1,3,2}

  1. x=100,99不在集合,起点;向后无,len=1
  2. x=4,3存在,不是起点,跳过
  3. x=200,199不在,len=1
  4. x=1,0不在集合,起点;向后找到2,3,4,len=4
  5. 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存储元素

总结&易错点

  1. 遍历set而不是原nums数组,规避重复数字重复计算。
  2. !set.contains(x‑1)是核心,去掉该条件会退化O(n²)超时。
  3. 空数组直接返回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

  1. 3入堆;2入堆,size=2
  2. 1入堆,size>2,poll弹出1;堆[2,3]
  3. 5入堆 size>2,poll弹出2;堆[3,5]
  4. 6入堆 size>2,poll弹出3;堆[5,6]
  5. 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)原地。

总结&易错点

  1. PriorityQueue默认小顶堆。
  2. 快速选择目标下标是 n‑k,不要直接用k。
  3. 快速选择修改原数组;不允许修改输入优先堆解法。

例题4 LC347 前K个高频元素

题目信息:返回数组出现频率前k高的元素。 示例:nums=[1,1,1,2,2,3],k=2,输出[1,2]

题意简述

按出现频次做TopK。

核心思路

  1. HashMap统计每个数字出现频次。
  2. 小顶堆存Map.Entry,比较频率value;维持堆大小k,超过k弹出频率最小。
  3. 遍历哈希表全部entry;最后取出堆内key返回。

手动模拟

map统计{1:3,2:2,3:1},k=2

  1. entry(1,3)入堆;entry(2,2)入堆 size=2
  2. entry(3,1)入堆 size>2,poll弹出(3,1);堆保留(2,2),(1,3)
  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)哈希表。

总结&易错点

  1. 堆比较频率value,不是key。
  2. 使用小顶堆,只保存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),原地修改数组

总结&易错点

  1. 距离计算要使用long,防止int数值溢出。
  2. 前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规避最坏情况 允许修改原数组场景

高频踩坑总览

  1. PriorityQueue默认是小顶堆,大顶堆必须传比较器。
  2. TopK:前K大用小顶堆;前K小用大顶堆,维持堆大小k。
  3. 数值平方计算注意int溢出,转long。
  4. 快速选择会修改原输入,如果业务不允许,不能使用。
  5. HashMap遍历entrySet()拿键值对;HashSet用来去重+O(1)查询。

配套笔记:二分查找、滑动窗口、单调栈、二叉树BFS层序遍历、本份哈希+堆TopK专项。