美文网首页
215. Kth Largest Element in an A

215. Kth Largest Element in an A

作者: FlynnLWang | 来源:发表于2016-12-26 21:47 被阅读0次

Question

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Code

Version 1 (sort):

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

Version 2 (heap):

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            pq.offer(nums[i]);
        }
        
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > pq.peek()) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }
}

Solution

方法一:直接排序,返回倒数第k个元素即可。
方法二:用小根堆。构建一个大小为k的小根堆,返回第一个元素即可。

相关文章

网友评论

      本文标题:215. Kth Largest Element in an A

      本文链接:https://www.haomeiwen.com/subject/llhsvttx.html