LeetCode :347. Top K Frequent Elements

347. Top K Frequent Elements

解题思路；

O(n)

• hash，得到<元素，频次>键值对
• 因为频次小于n，建散列表，即新建大小为n+1的数组，数组下标为频次，数组内容为有相同频次的键值list，对散列表按下标由大到小遍历，找出k个键值

O(n*log(n-k))

• hash map
• 新建大小为n-k的最大堆，遍历<元素, 频次>，频次大于堆顶的保存到返回列表，频次小于堆顶的入堆，最后最小堆保存的是出现频次最低的n-k个，被“舍弃”的元素则是出现频次最大的k个

下边这段代码是根据上述第一种O(n)的思路写的代码。在LeetCode中运行时间是32ms

    public static List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
      
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.get(nums[i])==null?1:map.get(nums[i])+1);
        }
        
        //定义类型为list的数组，此处并未对list进行初始化，数组下标为频率，对应的list的为此频率的element
        ArrayList[] arrayList=new ArrayList[nums.length+1];
        Iterator iterator=map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry entry=(Map.Entry) iterator.next();
            if(arrayList[(int) entry.getValue()]==null)
              arrayList[(int) entry.getValue()]=new ArrayList<>();//对list进行初始化
            arrayList[(int) entry.getValue()].add(entry.getKey());
        }
        List<Integer> result = new ArrayList<Integer>();
        //从后向前遍历arrayList，输出频率最高的前k个element
        for(int i=arrayList.length-1;i>=0&&k>0;i--){
            if(arrayList[i]==null)continue;
            for(int j=0;j<arrayList[i].size()&&k>0;j++){
                result.add((Integer)arrayList[i].get(j));
                k--;
            }
        }
        
        return result;
    }

下面的代码是别人写的代码也是实现思路一的代码，和我写的步骤是一样的，不过要简洁一些

    public static 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.get(n)==null?0: frequencyMap.get(n)+ 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;
    }

参考原文：http://blog.csdn.net/lilingyu520/article/details/51339878