Java解決Leetcode 347.前K個の高周波要素

1824 ワード

非空の整数配列が与えられ、周波数が現れる前にkの高い要素が返される.
例1:
入力:nums=[1,1,1,2,2,3],k=2出力:[1,2]例2:
入力:nums=[1]、k=1出力:[1]説明:
与えられたkは常に合理的であり、1≦k≦配列中の異なる要素の個数であると仮定することができる.あなたのアルゴリズムの時間的複雑さはO(n log n)より優れなければなりません.nは配列の大きさです.
 
このテーマの構想は周波数統計にtopK問題を加えることであるが,Javaコードで実現するのはやや難しい.
まず周波数を統計する必要があって、1つのHashMapで周波数を統計して、HashMapの伝わる汎用型に注意して必ず包装の類を使わなければなりませんここでHashMapのAPIの使用も技巧に注意します
統計周波数が最大の要素は、最小のスタックを使用する必要があります.ここで最小のスタックは匿名の内部クラスを転送し、Comparatorインタフェースを実現します.ここでは、現在のクラスで実装され、現在のクラスでHashmapをキャプチャするのは簡単です.したがって、クラスを定義する必要はありません.
次にHashMapを巡回する必要があります.反復器を使用して巡回することができます.ここでは強化forループを使用し、右側にhashMapを使用する小さなテクニックがあります.getKeysメソッド
最後に優先キューを1回巡り、強化forループをもう一度使用したり、キューをデキューしたりすることもできます.
順序性が要求される場合は、最後に逆順する必要があります.ここでは必要ありません.
class Solution {
    public List topKFrequent(int[] nums, int k) {
        HashMap hashMap = new HashMap<>();
        for(int num:nums){
            if(hashMap.containsKey(num)){
                hashMap.put(num,hashMap.get(num)+1);
            }else{
                hashMap.put(num,1);
            }
        }
        //    
        PriorityQueue pq = new PriorityQueue<>(new Comparator(){
            @Override
            public int compare(Integer a, Integer b) {
                return hashMap.get(a) - hashMap.get(b);
            }
         });

         for(Integer key:hashMap.keySet()){
             if(pq.size()hashMap.get(pq.peek())){
                 pq.remove();
                 pq.add(key);
             }
         }
         List list = new ArrayList<>();

         for(Integer key:pq){
             list.add(key);
         }
         return list;
    }
}

 
その匿名の内部クラスもLamda式で置き換えることができます