LeetCode【347】 Top K Frequent Elements

雨点打透心脏的1/2处 2022-05-11 14:22 110阅读 0赞

Given a non-empty array of integers, return the ***k*** most frequent elements.

**Example 1:**

Input: nums = [1,1,1,2,2,3], k = 2
    Output: [1,2]

**Example 2:**

Input: nums = [1], k = 1
    Output: [1]

### **思路：** ###

1、首先遍历数组，使用HashMap freq的存储每个数出现的频率——freq(num, 频率)；

2、遍历map，对频率进行排序，这里使用优先队列priorityQueue的方式维护出现频率最多的k个数

a.PriorityQueue pq的泛型为自定义的一个Pair类， pair(频率,num)，因为要对频率进行比较，因此频率就作为第一个数

b.优先队列用最小堆实现方式，只存储k个数，队首即为频率最小的pair

c.遍历map，当pq的size小于k值时一直往里边添加pair，当=k时获得队首pair，比较pair的频率和此时entry的值，前者小则               poll，offer进该entry（也就是一直维护pq为频率最多的k个数）

3、将pq中的值放入结果list中。

### 代码： ###

class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            //1. traversing the nums to get freq of every nums
            Map<Integer, Integer> freq = new HashMap<>();
            for(int num : nums){
                freq.put(num, freq.getOrDefault(num, 0) + 1);
            }
            //2. sort the freq，使用最小堆来维护出现频率最多的k个数
            PriorityQueue<Pair> pq = new PriorityQueue<>(k, idComparator);
            for(Map.Entry<Integer, Integer> entry : freq.entrySet()){
                if(pq.size()==k){
                    //取出pq中出现频率最少的元素，然后删除，再添加进此时的entry
                    if(pq.peek().getFreq() < entry.getValue()){
                        pq.poll();
                        pq.offer(new Pair(entry.getValue(), entry.getKey()));
                    }
                   
                }else{
                    pq.offer(new Pair(entry.getValue(), entry.getKey())); 
                }
            }
            System.out.println(pq.size());
            //3. 结果
            List<Integer> res = new ArrayList<>();
            while(!pq.isEmpty()){
                res.add(pq.peek().getNum());
                pq.poll();
            }
            return res;
        }
        
        //自定义匿名比较器(最小堆的方式)
        public static Comparator<Pair> idComparator = new Comparator<Pair>(){
            public int compare(Pair p1, Pair p2){
                return p1.getFreq() - p2.getFreq();
            }
        };
    }
    
    class Pair{
        private int freq;
        private int num;
        
        Pair(int freq, int num){
            this.freq = freq;
            this.num = num;
        }
        
        public void setFreq(int a){
            this.freq = a;
        }
        public int getFreq(){
            return freq;
        }
        
        public void setNum(int b){
            this.num = b;
        }
        public int getNum(){
            return num;
        }
    }

时间复杂度：遍历数组O(n),优先队列O(nlogk),总：O(nlogk)

### 知识点： ###

1、使用HashMap存储某数据中元素出现的次数。

2、优先队列：维护前k大哥元素或前k小个元素。

3、遍历Map的方法：

**a**.for-each循环中使用entry遍历

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
     
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
     
        entry.getKey();
        entry.getValue();
    }

**b**. 在for-each中循环keys或values

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
     
    for (int k: map.keySet()) {
     
        int value = map.get(k);
    }
    for (int v: map.values()) {
     
        ...
    }

**c**.通过iterator

HashMap<Integer, Integer> map = new HashMap<>();
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while(it.hasNext()){
        Entry<Integer, Integer> entry = it.next();
        entry.getKey();
        entry.getValue();
    }

其他：

看了discuss中快的部分答案，使用**桶排序**完成对频率的排序。

**思路：**

排序部分：按数据元素出现的频次进行排序，那么“桶”的数量范围是可以确定的——桶的数量小于等于给定数组元素的个数。编号为i的桶用于存放数组中出现频次为i的元素——即编号为i的桶存放map中值等于i的键。

排序完成后，编号大的桶中元素出现的频次高，因此，我们“逆序”(先取桶编号大的桶的元素)获取桶中数据，直到获取数据的个数等于k。

**discuss中代码：**

public List<Integer> topKFrequent(int[] nums, int k) {
    
    	List<Integer>[] bucket = new List[nums.length + 1];
    	Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
    
    	for (int n : nums) {
    		frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
    	}
    
    	for (int key : frequencyMap.keySet()) {
    		int frequency = frequencyMap.get(key);
    		if (bucket[frequency] == null) {
    			bucket[frequency] = new ArrayList<>();
    		}
    		bucket[frequency].add(key);
    	}
    
    	List<Integer> res = new ArrayList<>();
    
    	for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
    		if (bucket[pos] != null) {
    			res.addAll(bucket[pos]);
    		}
    	}
    	return res;
    }