在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
示例1：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例2：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度
Java解法
思路：
- 寻找第k大或第k个一般是通过快慢指针来处理的，但本题的情况是无序的，所以我没法通过一次遍历解决问题
- 考虑通过排序来处理，在快排算法中，是可以快速确定当前数字位置的，通过快排来处理
- 因为递归的缘故，所以效率没有很高
package sj.shimmer.algorithm.m4_2021;
/**
* Created by SJ on 2021/4/20.
*/
class D83 {
public static void main(String[] args) {
System.out.println(findKthLargest(new int[]{3,2,1,5,6,4},2));
System.out.println(findKthLargest(new int[]{3,2,3,1,2,4,5,5,6},4));
}
public static int findKthLargest(int[] nums, int k) {
return findIndex(nums, 0, nums.length - 1, k-1);
}
public static int findIndex(int[] nums,int start,int end, int k) {
int pivot = nums[start];
int left = start;
int right = end;
//降序排序
while (left < right) {
//从右向左寻找较大值
while (left < right && nums[right] <= pivot) {
right--;//找到比基准值小的数值的位置
}
if (left < right) {
//因为基准值已被记录，所以直接更新即可，args[end]会在下一次更新
nums[left] = nums[right];
}
//从左向右寻找较小值
while (left < right && nums[left]>= pivot) {
left++;//找到比基准值大的数值的位置
}
if (left < right) {
//因为基准值已被记录，所以直接更新即可，args[end]会在下一次更新
nums[right] = nums[left];
}
}
nums[left] = pivot;
if (left==k) {
return nums[left];
}else if (left>k){//往前半部分寻找
return findIndex(nums,start,left-1,k);
}else {
return findIndex(nums, left + 1, end, k);
}
}
}
D83.png
官方解
-
基于快速排序的选择方法
算法思想与我的思路一致
做的提升：切分数组时我的是已左起点为边界值来定位，在不同数据下容易切分为 1,2-n两个长度差异大的数组，这样效率提升不大，官方解引入了随机化这个边界值定位
- 时间复杂度：O(n)
- 空间复杂度：O(logn)
-
基于堆排序的选择方法
构建大堆，删除k-1次最大值，返回堆最大值
具体参考堆排序
