题目：数组中的第K个最大元素（Java）

内容

链接: 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

用例

1. 示例 1:

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

2. 示例 2:

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

思路

快排的思想。本文是从大到小排序。lo记录快排递归时候的起始位置，hi记录终止位置。通过partition()每次将需要排的子数组分成两半。j记录分隔位置。如果看k<j，说明要找的第K个最大元素在j的左边，只需要对左边接着排序。如果k>j，说明要找的第K个最大元素在j的右边。恰好等于，说明要找的第K个最大元素就在位置j，直接返回。
一开始int res = quickSort(nums, 0, nums.length - 1, k-1);，k-1是为了把下标和位置联系起来。如果数组只包含一位数，K=1,其实返回的是下标为0的元素。

AC代码

class Solution {
    public static int findKthLargest(int[] nums, int k) {
        int res = quickSort(nums, 0, nums.length - 1, k-1);
        return res;
    }


    public static int quickSort(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return nums[lo];
        }
        exchange(nums, lo, new Random().nextInt(hi-lo) + lo);
        int res = nums[lo];
        int j = partition(nums, lo, hi);

        if(k< j){
            return quickSort(nums, lo, j - 1 ,k);
        }else if(k> j){
            return quickSort(nums, j + 1, hi, k);
        }
            return res;
    }

    private static int partition(int[] nums, int lo, int hi) {
        int key = nums[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            while (nums[++i] > key) {
                if (i == hi)
                    break;
            }
            while (nums[--j] < key) {
                if (j == lo)
                    break;
            }
            if (i >= j)
                break;
            exchange(nums, i, j);
        }
        exchange(nums, lo, j);
        return j;
    }

    private static void exchange(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

提交记录

[1]: https://leetcode-cn.com/