TopK,得到答案并不难,但不断优化的过程,挺艰难。
题目描述:
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
1.全局排序,时间复杂度取决于排序算法,一般是 O(n*lgn)。 相信大多数朋友看到这题的思路就是排序,返回第k大的值,甚至还有小机灵鬼直接调用内置方法
public int findKth(int[] a, int n, int K) {
Arrays.sort(a);
return a[n-K];
}
2.局部排序,只排序TopK个数,O(n*k),冒泡、直接选择、直接插入都可以,但k的取值趋近n时,时间复杂度又趋近与O(n^2)。
public int findKth(int[] a, int n, int K){
// 冒泡k次
for (int i = 0; i < K; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr[n - K];
}
3.堆,TopK个数也不排序了,O(n*lg(k)),想练手的可以模仿堆排序手动维护小根堆。也可以使用最小优先队列。
public int findKth(int[] a, int n, int K){
// 暂存 第k大的值
PriorityQueue<integer> queue = new PriorityQueue<>(K);
// n * 调整 lgk
for (int num : a) {
if (queue.isEmpty() || num > queue.peek()) {
if (queue.size() >= K) {
queue.poll();
}
queue.add(num);
}
}
return queue.isEmpty() ? 0 : queue.peek();
}
上面的代码有bug,纠正代码 ↓↓↓
public int findKth(int[] a, int n, int K){
// 暂存K个较大的值,优先队列默认是自然排序(升序),队头元素(根)是堆内的最小元素,也就是小根堆
PriorityQueue<Integer> queue = new PriorityQueue<>(K);
// 遍历每一个元素,调整小根堆
for (int num : a) {
// 对于小根堆来说,只要没满就可以加入(不需要比较);如果满了,才判断是否需要替换第一个元素
if (queue.size() < K) {
queue.add(num);
} else {
// 在小根堆内,存储着K个较大的元素,根是这K个中最小的,如果出现比根还要大的元素,说明可以替换根
if (num > queue.peek()) {
queue.poll(); // 高个中挑矮个,矮个淘汰
queue.add(num);
}
}
}
return queue.isEmpty() ? 0 : queue.peek();
}
4.快速排序的思想--随机选择法,时间复杂度 O(n) 需要理解两个思想,快排的分治,二分查找的剪枝 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n)) 减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O(n) TopK的另一个解法:随机选择 + partition
以下是网上找到的一些伪代码在partition是从大到小排序,不符合个人的习惯。导致后续的伪代码都很难弄懂。
int RS(arr, low, high, k){
if(low == high) return arr[low];
i = partition(arr, low, high);
temp = i - low; //数组前半部分元素个数
if (temp >= k)
return RS(arr, low, i-1, k); //求前半部分第k大
else
return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}
于是自己摸索了好久,写出了以下代码,partition+二分法,其实要找第k大,前面的排序再取值已经知道了第K大的数,下标是len - k。那么partition能直接定位到len - k 的位置就找到了结果。如何找呢,就用到了二分查找的思想,不断接近len-k的位置,最终返回结果。
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
return quickSort(a, 0, a.length - 1, K);
}
private int quickSort(int[] arr, int left, int right, int k){
int p = partition(arr, left, right);
// 改进后,很特殊的是,p是全局下标,只要p对上topK坐标就可以返回
if (p == arr.length - k) {
return arr[p];
}else if (p < arr.length - k) {
// 如果基准在左边,这在右边找
return quickSort(arr, p + 1, right,k);
}else {
return quickSort(arr, left, p - 1,k);
}
}
private int partition(int[] arr, int left, int right) {
// 可优化成随机,或中位数
int key = arr[left];
while (left < right) {
while (left < right && arr[right] >= key) right--;
arr[left] = arr[right];
while (left < right && arr[left] <= key) left++;
arr[right] = arr[left];
}
arr[left] = key;
return left;
}
}
如果你觉得有帮助的话,求赞、求关注、求收藏。如果有疑问的话,请在下面评论,我会及时解答。 祝大家牛年大吉!AC 多多,Offer 多多!加油!