LeetCode[215] Kth Largest Element in an Array

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.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

分析:

PriorityQueue内部是由堆实现的。每次remove()都会将最小的元素删除。

建一个PriorityQueue,将数组元素都加入该队列。然后移出nums.length-k个,下一个出来的就是第K大的。

代码:

public class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> q = new PriorityQueue<Integer>();
for(int i = 0;i < nums.length;i++)
q.add(nums[i]);
for(int i = 0; i < nums.length - k;i++)
q.remove();
return q.peek();
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :