Top K Frequent Elements Java

你的名字 2022-05-28 06:24 166阅读 0赞

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.

题目大意就是要我们在nums数组中找出k个出现次数最多的数字，作为一个java类库的重度使用患者（懒鬼）我用了以下代码ac了，不过我深知代码还不够完善，比如出现的k个出现次数相同的数字也有在数组中的先后顺序，我并没用按这个顺序保存在link中

代码也很简单，先用hashmap存nums，key是数字，value是出现的次数，为了体现出现次数最多的k个数，我为了将map的value逆序排列，把map的entryset形式存到arraylist中，再修改comparator接口，实现逆序功能。最后按次数逆序添加k个到linklist里

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Map.Entry;
    
    public class TopK {
    	private static class ValueComparator implements Comparator<Map.Entry<Integer, Integer>> {
    		public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
    			return o2.getValue() - o1.getValue();
    		}
    
    	}
    
    	public List<Integer> topKFrequent(int[] nums, int k) {
    		Map<Integer, Integer> m = new HashMap<>();
    		List<Integer> l = new LinkedList<>();
    		List<Map.Entry<Integer, Integer>> al = new ArrayList<>();
    
    		for (int i = 0; i < nums.length; i++) {
    			m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
    		}
    
    		al.addAll(m.entrySet());
    		TopK.ValueComparator vc = new ValueComparator();
    		Collections.sort(al, vc);
    		
    		for (int i=0; i<k; i++) {
    			l.add(al.get(i).getKey());
    		}
    		
    		return l;
    
    	}
    }