leetcode215_数组中的第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

方法一：排序

function findKthLargest(nums, k) {
    var N = nums.length;
    nums.sort((a,b)=>a-b);    //从小到大排序，避免[1,10,2,...]的情况
    return nums[N - k];    //最大的是nums[N-1], 次大的是nums[N-2], ...
}
console.log(findKthLargest([3,2,1,10,5,6,4], 2));    //6

复杂度分析

时间复杂度 : O(Nlogk) 。向大小为 k 的堆中添加元素的时间复杂度为 O(logk)，我们将重复该操作 N 次，故总时间复杂度为 O(Nlogk)。

空间复杂度 : O(k) ，用于存储堆元素。

方法二：小顶堆

import java.util.PriorityQueue;
public class Solution {
    public static void main(String[] args) {
        int[] nums1 = {3,2,1,5,6,4};
        System.out.println(findKthLargest(nums1, 2));    //5
        int[] nums2 = {3,2,3,1,2,4,5,5,6};
        System.out.println(findKthLargest(nums2, 4));    //4
    }
    public static int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'    小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for (int n: nums) {
            heap.add(n);    // 添加
            if (heap.size() > k){    // keep k largest elements in the heap
                heap.poll();    // 从小顶堆的堆顶删除
            }
        }
        return heap.poll();
    }
}

复杂度分析

时间复杂度 : 平均情况 O(N) ，最坏情况 O($N^2$) 。

空间复杂度 : O(1) 。