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

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 ≤ 数组的长度。

思路一：排序后取值

复杂度分析：

时间复杂度：排序时间为O(nlogn),所以时间为O(nlogn)

空间复杂度：O(1)

思路二：利用堆

维持一个大小为K的最小堆，堆顶的元素始终是当前所有元素中第K大的元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();    // 最小堆
        for(int i : nums){
            heap.offer(i);
            if(heap.size() > k){
                heap.poll();        // 维持堆的大小为k
            }
        }
        return heap.poll();
    }
}

力扣测试时间为：6ms, 空间为40.2MB

复杂度分析：

时间复杂度：一个维持堆大小为k的过程，所以时间复杂度为O(Nlogk)

空间复杂度：O(k),也就是堆的大小

思路三：

借助快排的过程

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 借助快排的过程
        return quickSort(nums, 0, nums.length - 1, nums.length - k);
    }

    public int partition(int[] nums, int left, int right){
        // 选取第一个元素为主元
        int pivot = nums[left];
        
        while(left < right){
            while(left < right && nums[right] >= pivot){
                right--;
            }
            nums[left] = nums[right];

            while(left < right && nums[left] <= pivot){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    public int quickSort(int[] nums, int left, int right, int k){
        // 如果经过一轮快排分区后主元位置刚好是k，那么可以直接退出了
        int mid = partition(nums, left, right);
        if(mid == k){
            return nums[k];
        }else if(mid > k){
            return quickSort(nums, left, mid - 1, k);
        }else{
            return quickSort(nums, mid + 1, right, k);
        }
    }
}

力扣测试时间为9ms, 空间为40.6MB

复杂度分析：

时间复杂度：每次将数组分成两段，只会选择其中一段进行partition操作，所以时间复杂度为O(N+N/2 + N/4 + 1) = ，所以时间复杂度为O(N)

空间复杂度为：O(1)

 思路参考：

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode/