概述
目录
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 < Integer, Integer > map = new HashMap < > (); // 记录元素出现的次数
for(int i = 0; i < nums.length; i++) map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
int[][] array = new int[2][map.size()]; // 第一行是原数组，第二行是出现的次数
int i = 0;
for(Map.Entry < Integer, Integer > 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 < end) {
while(start < end && originArray[1][end] <= freq) // 从后往前找，找比基准值大的值为止
end--;
while(start < end && originArray[1][start] >= freq) // 从前往后找，找到比基准值小的值为止
start++;
if(start < end) swap(originArray, start, end); // 交换位置
}
swap(originArray, start, startIndex); // 基准点和重合点交换位置
return start;
}
private static void swap(int[][] originArray, int start, int end) {
for(int i = 0; i < originArray.length; 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)<arr(2*i+1) && arr(i)<arr(2*i+2)
2.2 利用PriorityQueue 实现大根堆
public static int[] topKFrequent1(int[] nums, int k) {
// 构造 HashMap。Key：nums 中的每个元素；Value：对应元素出现的次数（即频率）
HashMap < Integer, Integer > store = new HashMap < > ();
for(Integer num: nums)
store.put(num, store.getOrDefault(num, 0) + 1);
// 构造小根堆（即最小堆），用于保存前 k 个出现频率最高的元素
// 目的是让 minHeap 根据数字出现的频率进行升序排序（因为是小根堆，所以是升序）
PriorityQueue < Integer > minHeap = new PriorityQueue < > (Comparator.comparingInt(store::get));
for(Integer key: store.keySet()) {
if(minHeap.size() < k) // 填充 minHeap
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 < Integer, Integer > store = new HashMap < > ();
for(Integer num: nums)
store.put(num, store.getOrDefault(num, 0) + 1);
// 构造一个桶的集合（即一系列桶），桶的个数为 nums 的长度 +1，因为 buckets[0] 没有意义
// 目的是将出现频率为 i 的数放到第 i 个桶里（即 buckets[i]）
List < Integer > [] buckets = new List[nums.length + 1];
for(Map.Entry < Integer, Integer > 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 < buckets[i].size() && index < k; j++) {
res[index++] = buckets[i].get(j); // 依次将桶里的数字填充进 res 数组中
}
}
}
return res;
}
最后
以上就是生动招牌为你收集整理的TopK问题（快排变形/堆/二叉搜索树/计数排序）leetcode347 TopK问题描述1. 快排变形2. 大根堆（前K小）/小根堆（前K大）3. 桶排序的全部内容，希望文章能够帮你解决TopK问题（快排变形/堆/二叉搜索树/计数排序）leetcode347 TopK问题描述1. 快排变形2. 大根堆（前K小）/小根堆（前K大）3. 桶排序所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复