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.

解题要点：

PriorityQueue解法，Python有自带的方法，heapq.nlargest()，详情看下面code。Java版本需要注意的一点是，创建新PriorityQueue时，加上属性由之前创建好的记个数的map中的value（出现次数）来进行判断大额在顶端，小额在底部。具体看下面code。

Python：

import heapq
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        mydict = {}
        for n in nums:
            if n not in mydict:
                mydict[n] = 1
            else:
                mydict[n] += 1

        return heapq.nlargest(k, mydict.keys(), key = mydict.get)

Java：

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int n : nums){
            if(map.containsKey(n)) map.put(n, map.getOrDefault(n, 1) + 1);
            else map.put(n, 1);
        }        
        PriorityQueue<Integer> pq = new PriorityQueue<>((n1, n2) -> map.get(n1) - map.get(n2));

        for (int n : map.keySet()){
            pq.add(n);
            if(pq.size() > k) pq.poll();
        }
        List<Integer> res = new ArrayList<>();
        while(!pq.isEmpty()){
            res.add(pq.poll());
        }
        Collections.reverse(res);
        return res;
    }
}

解法二：（桶排序）

桶排序是把数字出现的次数作为index，把数字放在一个array里。

Java：

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(int num : nums){
            int count = freqMap.containsKey(num) ? freqMap.get(num) : 0;
            freqMap.put(num, count + 1);
        }
        
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int freq = entry.getValue();
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(entry.getKey());
		}

        List<Integer> res = new ArrayList<>();
        for(int i = bucket.length - 1; i >= 0 && res.size() < k; i--){
            if(bucket[i] != null)
                res.addAll(bucket[i]);
        }
        return res;
    }
}

Python：

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        mydict = {}
        for n in nums:
            if n not in mydict:
                mydict[n] = 1
            else:
                mydict[n] += 1

        bucket = [[] * (len(nums) + 1) for i in range(len(nums)+1)]
        for key, v in mydict.items():
            bucket[v].append(key)
        
        res = []
        i = len(bucket) - 1
        while len(bucket) > 0:
            if len(res) == k:
                break
            if len(bucket[i]) != 0:
                for ele in bucket[i]:
                    res.append(ele)
                bucket.pop()
                i-=1
            else:
                bucket.pop()
                i-=1
        return res