347. 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.

解法1： heap

比较直接的写法就是用heap，不过还有一种bucket sort的办法似乎更快，可以做到O(N)
C++

1

Java
有一个Java8的compare写法可以掌握一下(a,b) -> a.getValue() - b.getValue()

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
27
28
29
30
31
32
33
34
35
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        // map with keySet
        // [1,1,1,2,2,3]
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // Put each elements into priorityqueue
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();   // poll the smallest entry based on the frequency
            }
        }
        while (!queue.isEmpty()) {
            res.add(queue.poll().getKey());
        }
        return res;
    }
}

解法2： Bucket 思想

基本的思路是，先用一个hashmap存储每一个num出现的次数。
然后最大的可能出现的次数就是nums的长度，所以可以用一个数组，每一个元素是一个list，记录当前频率下的所有数字。
这样以来，最后只需要从大到小的扫描一遍就可以得到答案了。

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 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.getOrDefault(n, 0) + 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;
}