LeetCode刷题实战215：数组中的第K个最大元素 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 数组中的第K个最大元素，我们先来看题面：

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

题意

在未排序的数组中找到第 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 ≤ 数组的长度。

解题

利用快速排序，快速定位第k大的元素，具体可看代码注释

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

    int find(int[] nums, int s, int e, int k) {
        // 设定flag，默认用nums[s]
        int flag = nums[s];
        int ss = s;
        int ee = e;
        while(ss<ee) {
            // 从后向前找到第一个比flag大的数
            while(ss<ee && nums[ee] <= flag)
                ee--;
            // 交换flag和比flag大的数
            nums[ss] = nums[ee];
            nums[ee] = flag;
            // 从前向后找到第一个小于等于flag的数
            while(ss<ee && nums[ss] > flag)
                ss++;
            // 交换flag和比flag小的数
            nums[ee] = nums[ss];
            nums[ss] = flag;
        }
        // 返回结果
        if(ss + 1 == k)
            return nums[ss];
        // 找到的数比k小，更新s
        else if(ss + 1 < k)
            return find(nums, ss+1, e, k);
        // 找到的数比k大，更新e
        else
            return find(nums, s, ss-1, k);
    }
}