目录

 TopK问题描述

1. 快排变形

1.1 图解过程

1.2 快排实现

2. 大根堆（前K小）/小根堆（前K大）

2.1  大根堆和小根堆

2.2 利用PriorityQueue 实现大根堆

3. 桶排序

3.1 图解桶排序

3.2 实现

 TopK问题描述

TopK问题，不管是求前K大/前K小/第K大/第K小等，都有4种不错的方法喔：

1. O(N)：用快排变形最最最高效解决TopK问题

2. O(NlogK)：大根堆（前K小）/小根堆（前K大）

3. O(N): 桶排序

以 leetcode 347 题为例 https://leetcode-cn.com/problems/top-k-frequent-elements/

1. 快排变形

用快排变形最最最高效解决TopK问题 O(N)

先通过快排切分排好第K小的数，根据快排切分的性质，它左边的K - 1个数都小于等于它，因此它以及它左边的数就是我们要找的前K小的数。

1.1 图解过程

假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。

首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边。

方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

        6  1  2  5  9 3  4  7  10  8

 到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下。

        6  1  2 5  4  3  9  7 10  8

        第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。

        3  1 2  5  4  6  9 7  10  8

到此第一轮“探测”真正结束。剩下的以此类推即可。

1.2 快排实现

public static int[] topKFrequent(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Map map = new HashMap <> (); // 记录元素出现的次数
for(int i = 0; i int[][] array = new int[2][map.size()]; // 第一行是原数组，第二行是出现的次数
int i = 0;
for(Map.Entry entry: map.entrySet()) {
array[0][i] = entry.getKey();
array[1][i++] = entry.getValue();
}
return quickSort(array, 0, array[0].length - 1, k - 1);
}
/**
* 快速排序
*
* @param originArray 原数组
* @param start 开始下标
* @param end 结束下标
* @param target 目标下标
* @return
*/
private static int[] quickSort(int[][] originArray, int start, int end, int target) {
// 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数
int k = partition(originArray, start, end);
if(k == target) return Arrays.copyOfRange(originArray[0], 0, k + 1);
// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
return k > target ? quickSort(originArray, start, k - 1, target) : quickSort(originArray, k + 1, end, target);
}
/**
* 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
*
* @param originArray
* @param startIndex
* @param endIndex
* @return
*/
private static int partition(int[][] originArray, int startIndex, int endIndex) {
int freq = originArray[1][startIndex];
int start = startIndex;
int end = endIndex;
// 以起点作为基准
while(start while(start end--;
while(start = freq) // 从前往后找，找到比基准值小的值为止
start++;
if(start }
swap(originArray, start, startIndex); // 基准点和重合点交换位置
return start;
}
private static void swap(int[][] originArray, int start, int end) {
for(int i = 0; i int temp = originArray[i][start];
originArray[i][start] = originArray[i][end];
originArray[i][end] = temp;
}
}

2. 大根堆（前K小）/小根堆（前K大）

2.1  大根堆和小根堆

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图

我们对上面的图中每个数都进行了标记，上面的结构映射成数组就变成了下面这个样子

还有一个基本概念：查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：

大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆：arr(i)

2.2 利用PriorityQueue 实现大根堆

public static int[] topKFrequent1(int[] nums, int k) {
// 构造 HashMap。Key：nums 中的每个元素；Value：对应元素出现的次数（即频率）
HashMap store = new HashMap <> ();
for(Integer num: nums)
store.put(num, store.getOrDefault(num, 0) + 1);
// 构造小根堆（即最小堆），用于保存前 k 个出现频率最高的元素
// 目的是让 minHeap 根据数字出现的频率进行升序排序（因为是小根堆，所以是升序）
PriorityQueue minHeap = new PriorityQueue <> (Comparator.comparingInt(store::get));
for(Integer key: store.keySet()) {
if(minHeap.size() minHeap.offer(key);
else if(store.get(key) > store.get(minHeap.peek())) { // 只要满了，则推出最小值
minHeap.poll();
minHeap.offer(key);
}
}
int[] res = new int[k];
int i = 0;
while(!minHeap.isEmpty())
res[i++] = minHeap.poll();
return res;
}

3. 桶排序

一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

3.1 图解桶排序

3.2 实现

public int[] topKFrequent(int[] nums, int k) {
// 构造 HashMap。Key：nums 中的每个元素；Value：对应元素出现的次数（即频率）
HashMap store = new HashMap <> ();
for(Integer num: nums)
store.put(num, store.getOrDefault(num, 0) + 1);
// 构造一个桶的集合（即一系列桶），桶的个数为 nums 的长度 +1，因为 buckets[0] 没有意义
// 目的是将出现频率为 i 的数放到第 i 个桶里（即 buckets[i]）
List [] buckets = new List[nums.length + 1];
for(Map.Entry entry: store.entrySet()) {
if(buckets[entry.getValue()] == null) // 如果某个桶还未放入过数字（即未初始化），则初始化其为一个数组
buckets[entry.getValue()] = new ArrayList <> ();
buckets[entry.getValue()].add(entry.getKey());
}
int[] res = new int[k];
int index = 0;
for(int i = buckets.length - 1; i > 0; i--) { // 遍历每个桶
if(buckets[i] != null) { // 如果桶里有数字
for(int j = 0; j res[index++] = buckets[i].get(j); // 依次将桶里的数字填充进 res 数组中
}
}
}
return res;
}