卖萌的弱渣

I am stupid, I am hungry.

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

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.

Solution

Java Solution: bucket sort

(Top-K-Frequent-Elements.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // <freq, nums[i]->nums[j]->nums[...]>
        List<Integer>[] bucket = new List[nums.length+1];
        // <num[i], freq>
        Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
        for (int num: nums){
            freqMap.put(num, freqMap.getOrDefault(num,0)+1);
        }
        for (int key: freqMap.keySet()){
            int freq = freqMap.get(key);
            if(bucket[freq]==null)
                bucket[freq] = new LinkedList<Integer>();
            bucket[freq].add(key);
        }

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

}

Python Solution

  • Sort dict by value
1
2
3
4

import operator
x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
sorted_x = sorted(x.items(), key=operator.itemgetter(1))
sorted_x will be a list of tuples sorted by the second element in each tuple. dict(sorted_x) == x.
  • Sort dict by key
1
2
3

import operator
x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
sorted_x = sorted(x.items(), key=operator.itemgetter(0))
(Top-K-Frequent-Elements.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        hash_map = dict()
        for i in nums:
            if i in hash_map.keys():
                hash_map[i] += 1
            else:
                hash_map[i] = 1
        # sort dict by hash_map.value
        sorted_map = sorted(hash_map.items(), key=operator.itemgetter(1),reverse=True)

        ret = []
        for i,j in sorted_map:
            ret.append(i)
            k -= 1
            if k == 0:
                return ret
        return ret