LeetCode(Sort&Search)Top K Frequent Elements

2018-07-01

Top K Frequent Elements

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.

思路：首先想到了用map来存储每个数以及每个数对应出现的次数，然后关键的一点就来了，我们需要知道次数的大小顺序，而在我们定义的map中次数是在value位置，所以采用常规的比较方法无法完成我们想要的根据value对map进行排序，所以想到了利用自定义comparator的方法来排序，最后从排好序的结果集中取到我们需要的k个数即可。

java代码如下：

import java.util.Map.Entry;
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map=new HashMap<>();
        List<Integer> reslist=new ArrayList<>();
        int len=nums.length;
        if(len==0 || nums==null){
            return reslist;
        }
        if(k>len){
            return null;
        }
        //build a map that can represent Frequency if each number.
        for(int i=0;i<len;i++){
            if(map.containsKey(nums[i])){
                int value=map.get(nums[i]).intValue();
                map.put(nums[i],value+=1);
            }else{
                 map.put(nums[i],1);
            }
        }
        
        List<Entry<Integer, Integer>> list=new ArrayList<>(map.entrySet());
        //Customized Comparator
        Collections.sort(list,new Comparator<Entry<Integer, Integer>>(){
            public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2){
                if(o1.getValue()>o2.getValue()){
                    return 1;
                }
                if(o1.getValue()<o2.getValue()){
                    return -1;
                }
                return 0;
            }
        });
        
        for(int i=0;i<k;i++){
            int res=list.get(list.size()-1-i).getKey();
            reslist.add(res);
        }
        
        return reslist;
    }
}