算法通关村第十关—数组中第K大的数字(白银)

数组中第K大的数字

?LeetCode215数组中的第K个最大元素。给定整数数组nums和整数k,请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

示例1：
输入：[3,2,1,5,6,4]和k=2
输出：5
示例2：
输入：[3,2,3,1,2,4,5,5,6]和K=4
输出：4

?我们在后面堆的部分也会分析这个问题，这里看看如何基于快速排序来做。而且要直接改造一下上面的快排来解决，而不是另起炉灶，只有这样平时的练习才有效果。
?那为什么能用快速排序来解决呢？我们还是看上面排序的序列：{26,53,48,15,13,48,32,15}
第一次选择了26为哨兵，进行一轮的排序过程为：

?上面红框位置表示当前已经被赋值给了pivot或者其他位置，可以空出来放移动来的新元素了。可以看到26最终被放到了属于自己的位置上，不会再变化，而26的左右两侧可以分别再进行排序。
?这里还有一个关键信息，我们可以知道26的索引为3，所以递增排序之后26一定是第4大的元素。这就是解决本问题的关键，既然知道26是第4大，那如果我要找第2大，一定是要到右边找。如果要找第6大，一定要到左边找（当然，如果降序排序就反过来了)，而不需要的那部分就不用管了。这就是为什么能用快速排序解决这个问题。

力扣官方题解：

class Solution {
    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }
    public int findKthLargest(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }
}

自己写的快排

class Solution {
    int quicksort(int[] nums, int left, int right, int pos){
        if(left >= right) return nums[pos];

        int pivot = nums[right];
        int i = left - 1;
        if(left < right){
            for(int j = left; j < right; j++){
                if(nums[j] < pivot){
                    int temp = nums[j];
                    i++;
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }

        int pivotnum = i + 1;
        int temp = nums[pivotnum];
        nums[pivotnum] = nums[right];
        nums[right] = temp;

        if(pivotnum >= pos) return quicksort(nums, left, pivotnum - 1, pos);
        else return quicksort(nums, pivotnum + 1, right, pos);

    }

    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int pos = nums.length - k;
        return quicksort(nums, left, right, pos);

    }
}

自己一开始偷懒的代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}