力扣 215 数组中的第K个最大元素

题意：给定一个数组，找到第k个最大的元素

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

思想：快速排序

复杂度：时间O（nlogn)，空间O(n)

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);
    }
}