[排序 手写堆 快排模板] 215. 数组中的第K个最大元素（堆排序、快速排序 + 分治）
程序员文章站
2024-02-14 23:59:22
...
[排序 手写堆 快排模板] 215. 数组中的第K个最大元素（堆排序、快速排序 + 分治）
215. 数组中的第K个最大元素
题目链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
相同题目：剑指offer 40.
分类：
- 堆排序（PriorityQueue、手写堆）
- 快速排序（利用快排的partition分治）
题目分析
这题考的就是排序算法的应用，有多种实现方法，面试的话可以有很多考点。
思路1：Arrays.sort
Arrays.sort是升序排列，要的是第k大的元素，即为nums[n-k]
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
- 时间复杂度：O(NlogN)
- 空间复杂度：O(logN)
思路2：堆排序（适合大数据量）
堆排序可以分为两种方法：
- 方法1：小顶堆存放数组的所有元素，然后弹出n - k 次顶部节点，第n - k次弹出的顶部节点就是整个数组的第k大元素；
- 方法2：小顶堆存放数组的前 k个元素，然后后续元素只有 > 顶部节点才加入堆中，当所有节点都处理完毕时，顶部节点就是第k大元素。
实现上分为：使用java提供的PriorityQueue作为顶堆；自己手写顶堆。
因为方法2可以避免堆过大，维持堆的空间复杂度为O(K)，所以我们分别用PriorityQueue和用自己写的顶堆实现方法2。
为了加深对手写堆的理解，我们用手写堆分别实现方法1和方法2。
使用PriorityQueue（小顶堆（大小=k） + 大于顶部的入堆）
使用一个优先级队列PriorityQueue，但设置一个计数器以确保队列只保存k个元素。这样能降低空间复杂度。
优先级队列默认是小顶堆，我们先将前k个元素直接入队，此时队列里保存的nums的前k个元素，顶部保存的是这k个元素里的最小值。
然后，再取剩余的元素入队，剩余的元素每入队一个，就和顶部比较，如果新元素 > 顶部，则将顶部弹出，然后新元素入队。
剩余的元素都按这个操作处理。
最后，所有元素都处理完毕，此时堆中保存的就是nums数组最大的前K个元素，堆的顶部就是第k大的元素。
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将nums数组前k个元素入队
for(int i = 0; i < k; i++){
queue.offer(nums[i]);
}
//将剩余元素入队
for(int i = k; i < nums.length; i++){
//如果当前元素 > 顶部，就将顶部弹出，当前元素入队
int top = queue.peek();
if(nums[i] > top){
queue.poll();
queue.offer(nums[i]);
}
}
//此时堆顶部就是第k大的元素
return queue.peek();
}
}
- 时间复杂度：O(NlogN)，共N个元素入队，最差情况下每个元素入队都要做一次堆化，一次堆化是O(logN)，所以整体时间复杂度为O(NlogN)
- 空间复杂度：因为规定了队列最多只能保存k个元素，所以O(K)
手写堆（小顶堆（大小=n） + 全部元素入堆 + 弹出n-k次顶部）
该方法对整个数组建小顶堆，每次弹出的堆顶是当前堆内的最小元素，而第k大元素就第n-k小元素，所以第n-k次弹出的堆顶就是第k大元素。
具体分析见：
class Solution {
//堆排序主函数
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;//初始堆大小为数组大小
//在数组上建堆
buildMinHeap(nums, heapSize);
//将顶部删除+最后一个叶节点覆盖根部 + 重新对根节点做堆化（寻找第n-k个弹出的元素）
for(int i = 0; i < nums.length - k; i++){
nums[0] = nums[heapSize - 1];
heapSize--;
minHeapify(nums, 0, heapSize);
}
//最后根部元素就是第k大元素
return nums[0];
}
//建堆（小顶堆）
public void buildMinHeap(int[] nums, int heapSize){
int n = nums.length;
//从倒数第1个非叶节点开始直到根节点
for(int i = (n - 1) / 2; i >= 0; i--){
//每个非叶节点都执行一次调整函数
minHeapify(nums, i, heapSize);//传递数组、非叶节点的下标、堆的大小(为什么要传递堆的大小？见分析)
}
}
//小顶堆的调整函数（递归实现）
public void minHeapify(int[] nums, int parent, int heapSize){
int lchild = parent * 2 + 1, rchild = parent * 2 + 2;
int min = parent;//存放左右孩子中的较小节点下标
//先拿父节点和左孩子比较，取较小值的下标（孩子下标>=heapSize表示父节点没有该孩子节点）
if(lchild < heapSize && nums[lchild] < nums[min]){
min = lchild;
}
//再拿前面得到的较小点和右孩子比较，取较小值的下标
if(rchild < heapSize && nums[rchild] < nums[min]){
min = rchild;
}
//经过前面的if分支，如果当前节点的孩子都大于它，或当前节点为叶子节点，则min = parent，不会进入下面的分支而是退出该函数，表示完成这次调整
if(min != parent){
//交换min下标和parent下标
swap(nums, parent, min);
//这只是一次调整，还需要拿当前min位置的元素继续和它的左右孩子比较（进入下一层递归）
minHeapify(nums, min, heapSize);
}
}
//数组两元素交换
public void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
手写堆（小顶堆（大小=k） + 大于顶部的入堆）
class HeapSortK {
//获取top-k元素主函数
public int getTopK(int[] nums, int k){
int heapSize = k;//指定堆的大小
//先构建k个数的小顶堆：只对[0~k-1]的元素建堆，建立在nums上
buildMinHeap(nums, heapSize);
//再依次处理k及往后的元素
for(int i = k; i < nums.length; i++){
//元素>顶部才入堆 + 堆化
if(nums[i] > nums[0]){
nums[0] = nums[i];
//对根部做堆化
minHeapify(nums, 0, heapSize);
}
}
return nums[0];//顶部保存的就是第k大元素
}
...建堆、调整的代码和上面的实现相同。
}
思路3：利用快排partition实现分治（速度最快）
这个思路是基于快速排序的特点：选择一个枢轴pivot，经过一趟快排后，这个枢轴会位于它在有序数组里的最终位置，如果是降序排列，那么在它之前的元素都大于等于它，在它之后的元素都小于它。
利用这个特点我们可以用来解top-k问题，按数组下标来表示的话，数组的第k大元素就是降序数组里下标 = k-1的元素。
算法流程：降序快排 + 分治
一轮降序快排（实现partition函数）
1、设置两个指针left, right，初始时分别指向待排序范围的左右边界。选择数组中的一个元素作为枢轴pivot，通常随机选择一个数，或选择nums[left]。
2、双指针开始工作：
- right先移动，从后往前寻找第一个 >= pivot的元素，找到了之后将 nums[left] 和 nums[right] 交换，如果交换发生，则将left + 1；
- left后移动，从前往后寻找第一个 < pivot的元素，找到之后将nums[left] 和 nums[right]交换，如果交换发生，则将right - 1；
不断循环上面两个步骤，直到left == right时，退出循环，此时下标left就是pivot最终所在的位置，令：
nums[left] = pivot;//（易遗漏）
3、将pivot所在下标返回。
根据partition的返回值进行分治
前面选择了一个枢轴pivot后，经过一趟降序快排partition，返回它所在的下标 i ：
- 如果i == k - 1，说明当前元素就是第k大元素，返回nums[i]即可；
- 如果i > k - 1，说明第k大元素在[0,i-1]之中，继续在[0~i-1]范围内做快排，寻找第k-1个元素；
- 如果i < k - 1，说明第k大元素在[i + 1, n - 1]之中，继续在[i+1,n-1]范围内做快排，寻找第k-1个元素。
实现代码
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSort(nums, k, 0, nums.length - 1);
return nums[k - 1];
}
//快排主函数，当pivot是第k大元素时算法结束
public void quickSort(int[] nums, int k, int left, int right){
int index = partition(nums, left, right);
if(index == k - 1) return;
else if(index > k - 1) quickSort(nums, k, left, index - 1);
else if(index < k - 1) quickSort(nums, k, index + 1, right);
}
//一轮降序快排函数：选择nums[left]作为枢轴，在[left,right]内做一次partition，返回所在的下标
//发生填充的指针向内移动，另一个指针保持不动。直到两个指针相遇时，算法结束.
public int partition(int[] nums, int left, int right){
//取nums[left]作为枢轴pivot
int pivot = nums[left];
//直到left
while(left < right){
//从末尾开始寻找大于pivot的元素
while(right > left && nums[right] <= pivot) right--;
if(left == right) break;
nums[left++] = nums[right];
while(left < right && nums[left] > pivot) left++;
if(left == right) break;
nums[right--] = nums[left];
}
nums[left] = pivot;//最后将枢轴插入合适的位置
return left;
}
}