215. Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array.

Note that it is the k<sup>th</sup> largest element in the sorted order, not the k<sup>th</sup> distinct element.

Solution

直接排序数组，返回倒数第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution 2

采用优先级队列，将所有元素加入队列，采用倒序比较器。
挤出前k-1个值，然后返回第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            pq.add(num);
        }
        for(int i = 0; i < k-1; i++){
            pq.poll();
        }
        return pq.peek();
    }
}