Top K 问题解决方案

Top K问题描述

从 n 个数中，找到 最大的 或者 最小的 前K 个数。（k 远远 小于 n）

Top K问题 解决方案

1. 使用排序算法排序，然后取 前 k 个 值 ------ 这个方案不是最优解
2. 使用大顶堆或者小顶堆 解决

• 找出最大的前K个数举例
  • 新建一个小顶堆
  • 扫描n个整数
    • 先将遍历的前k个数放入堆中
    • 从第 k + 1 个数开始，如果大于堆顶元素，就使用replace操作（删除堆顶元素，将 k + 1 个数放入到堆中）
  • 扫描完毕后，堆中剩下的数就是最大的前K个数。
• 找出最小的前K个数举例
  • 用大顶堆
  • 如果小于堆顶元素，就用replace操作

具体举例：剑指 Offer 40. 最小的k个数

问题描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
1
2
3
4

解题思路

使用大顶堆、小顶堆 方式是最优的

如果需要找到最小的 前k个数
1、创建一个大顶堆，然后 往里 add k个值
2、然后再遍历其他的元素， 假如到大顶堆，判断如果有 比 大顶堆最大的数小的值，那么进行替换
3、最后 大顶堆里面剩下的大顶堆中的 k个数，就是 最小的前k个数

代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) {
            return vec;
        }
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        
        for (int i = 0; i < arr.length; i++) {
            if (i < k) {
                queue.offer(arr[i]);
            } else {
                if (queue.peek() > arr[i]) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
         for(int i = 0; i < k; i++) {
                vec[i] = queue.poll();
            }
            return vec;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28