数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

使用快速选择算法，快速选择每一趟结束之后，就找到了哨兵最终的位置，并且哨兵左边的所有元素都小于等于哨兵，右边的元素都大于等于哨兵，跟据下标判断要返回的元素在左边还是右边，只递归其中一边，平均时间复杂度是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int n = 0;
    public int findKthLargest(int[] nums, int k) {
        n = nums.length;
        return find(nums,0,n-1,k);
    }
    private int find(int[] nums,int l, int r,int k){
        if(l==r) return nums[l];
        int mid = nums[l+r>>1];
        int i = l-1;
        int j = r+1;
        while(i<j){
            while(nums[++i]<mid);
            while(nums[--j]>mid);
            if(i<j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        if(n-k>=j+1){
            return find(nums,j+1,r,k);
        } else {
            return find(nums,l,j,k);
        }
    }
}