215. 数组中的第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
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

针对这个题目，我们首先想到的就是先用排序算法对数据从大到小进行排序，然后直接返回降序后的第 K 个元素即可。

另外，我们也可以借鉴快速排序的思想。每次选取一个 pivot，将大于 pivot 的数放在 pivot 左边，将小于 pivot 的数放在 pivot 右边。

这时候，如果 pivot 正好是第 K 个数据，则 pivot 就是数组中的第 K 个最大元素。

image.png

如果 pivot 所在的位置小于 K ，则说明数组中的第 K 个最大元素位于 pivot 的右边。此时，假设 pivot 的位置为 which_max，which_max 是几就代表 pivot 是数组中的第几个最大元素。这时候，我们再从 pivot 右边的数据中找到第 (K-which_max) 个最大元素即可。

image.png

如果 pivot 所在的位置大于 K ，则说明数组中的第 K 个最大元素位于 pivot 的左边。这时候，pivot 左边的数据全部大于 pivot，我们继续从 pivot 左边的数据中找第 K 个最大元素即可。

image.png

 public int findKthLargest(int[] nums, int k) {
        return quickSortRecursion(nums, 0, nums.length - 1, nums.length - k);
    }


    public int quickSortRecursion(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return nums[left];
        }

        int pivot = quickSortPartition(nums, left, right, k);

        if (pivot == k) {
            return nums[pivot];
        }

        if (k > pivot) {
           return quickSortRecursion(nums, pivot + 1, right, k);
        } else {
            return  quickSortRecursion(nums, left, pivot - 1, k);
        }

    }

    Random random=new Random();
    //对 nums[left...right] 进行partition操作 使得
    // nums[left...partitionIndex]>val  nums[partitionIndex+1...right]<val
    public int quickSortPartition(int[] nums, int left, int right, int k) {

        //增加随机
        int pivot = random.nextInt(right - left + 1) + left;
        swap(nums, pivot, left);
        int val = nums[left];
        pivot=left;

        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < val) {
                //相同索引 避免swap
                if((pivot+1)!=i) {
                    swap(nums, pivot + 1, i);
                }
                pivot++;
            }
        }

        swap(nums, left, pivot);
        return pivot;
    }


    private void swap(int[] nums, int source, int target) {
        int temp = nums[source];
        nums[source] = nums[target];
        nums[target] = temp;
    }

参考：https://www.cnblogs.com/seniusen/p/9810028.html