难度说明：🟢简单🟡中等🔴困难

堆

​ 堆的应用场景：类似一些求"前K....."概念的场景题

🟡01-数组中第K个最大元素（215）

1.题目内容

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

2.题解思路

👻方法1：排序法

​ 将数组按照逆序进行排序，然后输出nums[k]

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 将数组元素按照逆序排序，然后返回nums[k]，排序可以借助工具类进行排序，此处可以使用冒泡排序
        for (int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                if(nums[i] < nums[j]) {
                    // 逆序排序，将较小的值交换到后排
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        // 返回排序后第K个最大元素（数组下标从0开始）
        return nums[k-1];
        // 如果是降序排序，则返回nums[n-k]
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法2：快速排序法

public class Solution {
    private int quickSelect(List<Integer> nums, int k) {
        // 随机选择基准数
        Random rand = new Random();
        int pivot = nums.get(rand.nextInt(nums.size()));
        // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot)
                big.add(num);
            else if (num < pivot)
                small.add(num);
            else
                equal.add(num);
        }
        // 第 k 大元素在 big 中，递归划分
        if (k <= big.size())
            return quickSelect(big, k);
        // 第 k 大元素在 small 中，递归划分
        if (nums.size() - small.size() < k)
            return quickSelect(small, k - nums.size() + small.size());
        // 第 k 大元素在 equal 中，直接返回 pivot
        return pivot;
    }
    
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        return quickSelect(numList, k);
    }
}

👻方法3：堆（大顶堆、小顶堆）

​ PriorityQueue ：Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示

​ 所谓大小顶堆指的是：

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值
• 小顶堆：每个结点的值都小于或等于其左右孩子结点的值

​ 此处前K有两种思路，可以通过大顶堆或者小顶堆实现，例如此处找前K大的元素，其各自实现思路分析如下：

• 大顶堆：所有数据存入大顶堆，因此弹出堆顶元素，取出第K个元素，即为第K大的元素
• 小顶堆：定义一个存K个元素的小顶堆，堆顶元素是当前堆的最小值。先依次存入K个元素，然后剩余N-K个元素则依次与当前堆顶进行比较，如果发现cur>top(堆顶元素)，则说明其可以挤掉top跻身前K，以此类推，直到所有元素遍历完成，而堆顶元素就是第K大的元素

​ 结合两种方式可以发现，可以结合存储和检索效率进行分析：

• 大顶堆：需将所有元素入堆，构建的是一个全量的堆（存储了数组的所有元素），栈顶存储的是整个数组最大的数，拿到第K大的数需要弹出K-1个栈顶元素，第K个堆顶元素才是想要的结果
• 小顶堆：定义的是存储K个元素的小顶堆，这个堆存储的是位于前K的元素，栈顶元素即为为第K大的元素，需要插入元素过程中判断栈顶元素和插入元素的值，进而更新前K序列

​ 核心思路：借助PriorityQueue进行操作，结合小顶堆的特性，小顶堆每个节点的值都小于或等于其左右节点的值，换个角度理解小顶堆的root就是当前所有堆元素的最小值，基于此可以构建一个K个元素的小顶堆来进行操作（节省操作内容空间，栈顶元素就是第K大的元素）

​ 当数组有K个元素时，构建一个K个元素的小顶堆，那么此时堆顶就是第K大的数（也是当前堆的最小值）；

​ 基于此，当数组有N个元素时，前K个元素构建一个K个元素的小顶堆（此处堆顶为当前堆的最小值），然后堆剩余N-K个元素进行遍历，判断是否存在比当前堆顶大的值（如果比当前堆顶大，则说明该元素可以取代堆顶跻身于前K），也就是说与堆顶的比较有两种情况考虑

• 比堆顶大：可以跻身前K，如果其要跻身前K则起码会顶掉一个位置，被顶掉的这个位置就是小顶堆的堆顶，可以借助Java的PriorityQueue小顶堆的操作方法来操作堆顶元素：实际就是弹出堆顶、插入更大的元素，在这个插入的过程中可能涉及到堆的调整（让大元素下沉），这点交由工具类实现
• 比堆顶小：连当前堆的最小值都比不过，不符合前K的要求，无需做任何操作

​ 当所有元素遍历完成，最终也就完成了小顶堆的构建，而这个堆中最终存储的就是前K大的元素，且小顶堆的堆顶就是第K大的元素

// 堆（优先队列）
public int findKthLargest(int[] nums, int k) {
    // 基于Java提供的PriorityQueue构建小顶堆
    PriorityQueue<Integer> queue = new PriorityQueue();

    // 遍历数组的前k个元素，将它们加入最小堆中
    for (int i = 0; i < k; i++) {
        queue.offer(nums[i]);
    }

    // 遍历数组的剩余元素
    for (int i = k; i < nums.length; i++) {
        // 如果当前元素大于堆顶元素（即堆中最小的元素），则替换掉堆顶元素
        if (nums[i] > queue.peek()) {
            queue.poll(); // 移除堆顶元素
            queue.offer(nums[i]); // 添加新的较大元素到堆中
        }
        // 注意：这里不需要else，因为此处只关心当nums[i]大于堆顶时的情况。如果nums[i]小于等于堆顶，那么它就不会成为前k大的元素之一
    }

    // 堆顶元素即为第k大的元素，返回它
    return queue.peek();
}

补充思考题：如何从一个存有10亿个数字的文档中获取到最大的10个数，计算机内存只有1M?

​ 考虑10亿个数据很多，一次性无法装到计算内存中，采用常用的排序算法，可能也是不好进行操作，数据量很大这个地方可以想到可以才用小顶堆来解决这个问题：

• 让计算机去io读取文件
• 把读取出来的数据去构建一个包含10个元素的小顶堆
• 构建完成后，每次从文件中读取出来的一个数字和堆顶的元素进行比较，如果比堆顶元素小，就直接丢弃或者跳过。如果读取出来的数据比堆顶元素大，那么就可以用这个元素替代堆顶元素，进行调整小顶堆。这个算法的时间复杂度是O((100亿-1000)0g(1000)，即O(N-M)logM)，空间复杂度是M

​ 类似地，如果此处求的是第K小的元素，则采用K个元素的大顶堆进行存储，此时大顶堆存储的元素是当前的最大值，如果后面遍历的元素比这个堆顶还小，同理说明跻身前K小，以此类推。上述题目思路也可以反向说明求第K大的元素即求第N-K小的元素，然后转为大顶堆的实现思路

​

🟡02-前K个高频元素（347）

1.题目内容

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

2.题解思路

​ 结合题意分析，数组元素可能重复出现，且不同元素的出现频率都可能相同（k的取值是（1，数组中不相同元素的个数））

👻方法1：暴力法

​ 核心：计算频次+排序

​ 通过循环数组进行计数，借助额外空间存储每个不相同元素的出现频率，然后进行排序，返回前K个高频元素。

​ 那么此处题意则可转化为先计数，然后选择合适的排序算法，"前K"概念思路又可以参考前面的"第K大的元素"思路。如果采用小顶堆存储元素的话，此处存储的不是元素出现频次而是实际元素（可以通过自定义排序规则来实现小顶堆的存储：自定义排序规则比较的是元素对应出现的频率），然后遍历取出小顶堆的元素即可

/**
 * 347.前K个高频元素
 */
public class Solution {

    // 思路：计算元素出现频次、排序（前K高频概念采用小顶堆：自定义排序规则、遍历小顶堆）
    public int[] topKFrequent(int[] nums, int k) {

        // 借助哈希表存储元素出现频次（<元素值，对应出现频次>）
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        // 1.统计频次
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                // 元素存在则更新出现频次
                map.put(nums[i], map.get(nums[i]) + 1);
            }else{
                // 元素不存在则初始化
                map.put(nums[i],1);
            }
        }

        // 2.构建小顶堆存储（自定义排序规则:小顶堆元素存储的是不同的元素值，其排序规则需自定义根据map获取key相应的频次进行比较）
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });

        // 遍历Map集合，构建k个元素的小顶堆
        Set<Integer> set = map.keySet();
        Iterator<Integer> iterator = set.iterator();
        for(int i = 0 ; i < k ; i++){
            queue.add(iterator.next());
        }
        // 对于剩余的元素，则依次和小顶堆的堆顶元素（前K最小值）进行比较
        while(iterator.hasNext()){
            int cur = iterator.next();
            // 如果cur对应的频次大于堆顶元素则进行替换(注意此处比较的是频次，而堆中存储的是元素)
            if(map.get(cur)>map.get(queue.peek())){
                queue.remove(); // 堆顶元素弹出
                queue.offer(cur); // 插入当前较大的元素
            }// else 情况不考虑（不满足跻身前K的条件则不做任何操作）
        }

        // 3.遍历生成的小顶堆，返回结果集
        int[] res = new int[k];
        int idx = 0;
        while(queue.size()>0){
            res[idx++] = queue.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        Solution solution = new Solution();
        int[] res = solution.topKFrequent(nums, 2);
        System.out.println(Arrays.toString(res));
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

​ 扩展说明：可以构建大顶堆（所有数据入队），然后取前K个元素

class Solution {
   public int[] topKFrequent(int[] nums, int k) {
       HashMap<Integer, Integer> map = new HashMap<>();
       for(int n:nums){
           map.put(n,map.getOrDefault(n,0)+1);
       }
   		// 从大到小排序，这样后面取前k个元素就可以了
       PriorityQueue<Integer> pq = new PriorityQueue((e1, e2) -> map.get(e2) - map.get(e1));
       for(int key:map.keySet()){
           pq.add(key);
       }

       int[] res=new int[k];
       for (int i = 0; i < k; i++) {
           res[i]=pq.poll();
       }
       return res;
   }
}


// 注解说明
public class Solution2 {

    // 思路：计算元素出现频次、排序（前K高频概念采用大顶堆，自定义排序规则，所有数据入库，循环遍历取前K个栈顶元素）
    public int[] topKFrequent(int[] nums, int k) {

        // 借助哈希表存储元素出现频次（<元素值，对应出现频次>）
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        // 1.统计频次
        for (int i = 0; i < nums.length; i++) {
            // 元素存在则更新出现频次，元素不存在则初始化次数为1
            map.put(nums[i], map.getOrDefault(nums[i],0) + 1); // 如果key不存在则返回value为0（消除if...else...）
        }

        // 2.构建大顶堆存储（自定义排序规则:小顶堆元素存储的是不同的元素值，其排序规则需自定义根据map获取key相应的频次进行比较）
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o2) - map.get(o1);
            }
        });

        // 遍历Map集合，构建大顶堆（依次将集合元素入堆）
        Set<Integer> set = map.keySet();
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            queue.add(iterator.next());
        }

        // 3.遍历大顶堆，直接获取前K个元素
        int[] res = new int[k];
        for(int i=0;i<k;i++) {
            res[i] = queue.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        Solution2 solution = new Solution2();
        int[] res = solution.topKFrequent(nums, 2);
        System.out.println(Arrays.toString(res));
    }
}