题目描述

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

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

思路

先对数组排序（快速排序），在访问第k大的数 nums[len - k]，其中len为数组长度

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if(len == 1) return nums[0];
        fastSort(nums,0,len -1);
        return nums[len - k];
    }
    public void fastSort(int[] nums, int start, int end){
        if(start >= end) return;
        int key = nums[start];
        int left = start, right = end;
        while(left < right){
            while(left < right && nums[right] >= nums[left])
                right--;
            nums[left] = nums[right];
            while(left < right && nums[left] <= nums[right])
                left++;
            nums[right] = nums[left];
        }
        nums[left] = key;
        fastSort(nums,start,left - 1);
        fastSort(nums,right + 1, end);
    }
}

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(1)