Kth Largest Element in an Array,Top K Frequent Elements
文章目录
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.
1.解题思路
PriorityQueue,默认就是队列顶端是最小元素,第k大元素,我们只要限制queue的大小为k即可,最后队列顶端的就是第k大元素。
2.代码
public class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0) return -1;
PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
for(int i=0;i<k;i++){
pq.add(nums[i]);
}
for(int i=k;i<nums.length;i++){
if(nums[i]>pq.peek()){
pq.poll();
pq.add(nums[i]);
}
}
return pq.peek();
}
}
Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
1.解题思路
利用HashMap存入<num[i],count>,之后采用PriorityQueue,并限制最多放k个元素。
2.代码
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res=new ArrayList<Integer>();
if(nums.length==0) return res;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();//<num[i],count>
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
PriorityQueue<Map.Entry<Integer,Integer>> pq=new PriorityQueue<Map.Entry<Integer,Integer>>(new Comparator<Map.Entry<Integer,Integer>>(){
public int compare(Map.Entry<Integer,Integer> a,Map.Entry<Integer,Integer> b){
return a.getValue()-b.getValue();
}
});
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
pq.add(entry);
if(pq.size()>k)
pq.poll();
}
while(pq.size()>0){
Map.Entry<Integer, Integer> entry=pq.poll();
res.add(0,entry.getKey());
}
return res;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论