[leetcode]347. Top K Frequent Elements

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]

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.

Solution:

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) {
            return list;
        }
        Map<Integer, Integer> map = new HashMap();
        for(int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num)+1);
            }else {
                map.put(num,1);   
            }
        }
        
        return map.entrySet().stream().sorted((e1,e2) -> {
            if(e1.getValue() > e2.getValue()) {
                return -1;
            }else if(e1.getValue() < e2.getValue()){
                return 1;
            }else {
                return 0;
            }
        }).limit(k).map(e -> e.getKey()).collect(Collectors.toList());
        
        
    }
}

把map变为list。

比较大小的时候，a和b比较，如果你觉得a应该比较大，那么返回一个正值；b比较大，那么返回一个负值；一样大，就返回0。

以上为从小到大排序。如果要从小到大，相反即可。