<fieldset id="gc0si"></fieldset>

<abbr id="gc0si"></abbr>

<fieldset id="gc0si"><menu id="gc0si"></menu></fieldset><abbr id="gc0si"></abbr>

<del id="gc0si"></del>

<abbr id="gc0si"></abbr><strike id="gc0si"><menu id="gc0si"></menu></strike>

Kth Largest Element in an Array，Top K Frequent Ele

Tony_Zby 發(fā)布于2019-08-16 10:27 / 1443人閱讀

摘要：解題思路，默認(rèn)就是隊列頂端是最小元素，第大元素，我們只要限制的大小為即可，最后隊列頂端的就是第大元素。代碼解題思路利用存入，之后采用，并限制最多放個元素。

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，默認(rèn)就是隊列頂端是最小元素，第k大元素，我們只要限制queue的大小為k即可，最后隊列頂端的就是第k大元素。
2.代碼

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length==0) return -1;
        PriorityQueue pq=new PriorityQueue();
        for(int i=0;ipq.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存入，之后采用PriorityQueue，并限制最多放k個元素。

2.代碼

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res=new ArrayList();
        if(nums.length==0) return res;
        Map map=new HashMap();//
        for(int i=0;i> pq=new PriorityQueue>(new Comparator>(){
            public int compare(Map.Entry a,Map.Entry b){
                return a.getValue()-b.getValue();
            }
        
            });
       for(Map.Entry entry:map.entrySet()){
           pq.add(entry);
           if(pq.size()>k)
            pq.poll();
       }     
       while(pq.size()>0){
          Map.Entry entry=pq.poll();
          res.add(0,entry.getKey());
       } 
       return res;
    }
}