leetcode(前K個の高周波要素セット)

leetcode-347:前K個の高周波要素セット記述:非空の整数配列が与えられ、周波数前kの高い要素が現れる.入力:nums=[1,1,1,2,2,3],k=2出力:[1,2]構想:

本題は、優先キューの古典的な問題(1000000要素のうち上位100名を選択)であり、すなわち、N要素のうち上位k要素

を選択する.

をソートするとアルゴリズムの複雑さはNlogn

である.

は優先キューを使用し、アルゴリズムの複雑さはNlogkが優先キューを使用し、現在見ている前のk要素を維持し、最小スタックを使用する必要がある.

最初のコードを指定してから、一歩一歩最適化します:(1)先にカスタマイズした優先キューで実装します.

import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

public class Solution {
    private class Freq implements Comparable {
        int e, fre;
        public Freq(int e, int fre) {
            this.e = e;
            this.fre = fre;
        }

        @Override
        public int compareTo(Freq another) {//     ，    ，     
            if(this.fre < another.fre) {
                return 1;
            } else if(this.fre > another.fre) {
                return -1;
            } else {
                return 0;
            }
        }
    }

    public List topKFrequent(int[] nums, int k) {
        //    
        TreeMap map = new TreeMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //        K   
        PriorityQueue pq = new PriorityQueue<>();
        for(int key : map.keySet()) {
            if(pq.getSize() < k) {
                pq.enqueue(new Freq(key, map.get(key)));
            } else if(map.get(key) > pq.getFront().fre) {
                pq.dequeue();
                pq.enqueue(new Freq(key, map.get(key)));
            }
        }
        LinkedList res = new LinkedList<>();
        while (!pq.isEmpty()) {
            res.add(pq.dequeue().e);
        }
        return res;
    }
}

(2)Javaの優先キューを使用する(Java優先キューの最下位のデフォルトは最小スタックであることに注意)

import java.util.*;
class Solution {
    public class Freq implements Comparable {
        int e, freq;
        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
        @Override
        public int compareTo(Freq another) {//     
            if(this.freq > another.freq) {
                return 1;
            } else if(this.freq < another.freq) {
                return -1;
            } else {
                return 0;
            }
        }
    }
    public List topKFrequent(int[] nums, int k) {
        //    
        TreeMap map = new TreeMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //        k          
        PriorityQueue pq = new PriorityQueue<>();
        for(int key : map.keySet()) {
            if(pq.size() < k) {
                pq.add(new Freq(key, map.get(key)));
            } else if(map.get(key) > pq.peek().freq) {
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }
        }
        
        LinkedList res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(pq.remove().e);
        }
        return res;
        
    }
}

(3)コンパレータでコードを簡略化する:

import java.util.*;
class Solution {
    public class Freq {
        int e, freq;
        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
    }
     
    public class FreComparator implements Comparator {//     
        public int compare(Freq a, Freq b) {
            return a.freq - b.freq;
        }
    }
    public List topKFrequent(int[] nums, int k) {
        //    
        TreeMap map = new TreeMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //        k          
        PriorityQueue pq = new PriorityQueue<>(new FreComparator());
        for(int key : map.keySet()) {
            if(pq.size() < k) {
                pq.add(new Freq(key, map.get(key)));
            } else if(map.get(key) > pq.peek().freq) {
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }
        }
        
        LinkedList res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(pq.remove().e);
        }
        return res;
    }
}

(4)匿名クラスでコードをさらに簡略化する:

import java.util.*;
class Solution {
    public List topKFrequent(int[] nums, int k) {
        //    
        TreeMap map = new TreeMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //        k          
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for(int key : map.keySet()) {
            if(pq.size() < k) {
                pq.add(key);
            } else if(map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        
        LinkedList res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;        
    }
}

(5)lambda関数を用いてコードをさらに簡略化する:

import java.util.*;
class Solution {
    public List topKFrequent(int[] nums, int k) {
        //    
        TreeMap map = new TreeMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //        k          
        PriorityQueue pq = new PriorityQueue<>(
            (a, b) -> map.get(a) - map.get(b)
        );
        for(int key : map.keySet()) {
            if(pq.size() < k) {
                pq.add(key);
            } else if(map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        
        LinkedList res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;      
    }
}