LeetCode 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.
题目大意：
给定一个非空整数数组，返回其前k个出现次数最多的元素。
注意：
你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。
你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。
解题思路：
这是经典题，解法是HeapSelect：求最大k个数，就先对前k个元素建最小堆，然后遍历k到最后一个数，若它大于栈顶就替换且做minHeapify。最后结果是
最大的k个数在数组的前k个位置且堆顶（数组第一个数）为k个数的最小。堆并没有排序。
结果并不需要从大到小输出。
- 统计词频
- 建key-value数组
- heapSelect
- 把数组前k个数加入到结果集中
注意事项：
- 如果需要按大到小输出结果，需要对result进行排序O(klogk)，数组第一个也就是最小堆堆顶是这k个数中最小。
- key-pair版堆选择算法。
Python代码：
1 | from heapq import heapreplace, heappush |
统计词频部分可以用Counter优化。freq_dict有两个作用：将key和频率互换，还可以将dict转换成list方便和k比较1
2
3
4
5
6
7
8
9
10
11
12
13
14from heapq import heapreplace, heappush
from collections import Counter
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dict = Counter(nums)
freq_dict = [(v, k) for k, v in dict.items()]
res = []
for i in range(len(freq_dict)):
if i < k:
heappush(res, freq_dict[i])
elif freq_dict[i][0] > res[0][0]:
heapreplace(res, freq_dict[i])
return [v for k, v in res]
Java代码：
1 | public List<Integer> topKFrequent(int[] nums, int k) { |
算法分析：
时间复杂度为O(nlogk)，空间复杂度O(1)。时间复杂度是O(n)+O(nlogk),空间复杂度为O(m)+O(1),m为不重复的元素个数(unique element)。
算法II解题思路：
此题关于数组频数，所以考虑用桶排序(bucket sort)
- 统计词频（元素->频数）
- 桶排序：n+1个桶（n为原数组大小），把元素放入频数对应的桶号（频数->元素），用List把这些元素串起来。
- 逆序（从大到小）遍历不为空的桶，输入结果直至k个。
与上面算法不同的是结果是从大到小输出。数据类型有两个HashMap存储元素对应的频数，而List数组List[]反过来存储频数对应的元素。
注意事项：
- 桶排序要用List串联起元素，例如[1,2],k=2，频数为1的元素有两个，所以桶的内容应该是List。Python用[[] for _ in range(len(nums) + 1)]
- 桶数量为原数组大小+1，例如一个元素[1], 它的频数为1，而频数为0是不会出现。
- 逆序遍历所有桶，只要结果集个数为k，就停止循环。
Python代码：
1 | from collections import Counter |
Java代码：
1 | public List<Integer> topKFrequent2(int[] nums, int k) { |
算法分析：
时间复杂度为O(n)，空间复杂度O(n)。时间复杂度是O(n)+O(n),空间复杂度为O(m)+O(n),m为不重复的元素个数(unique element)。
Follow-up:
- 题目可以包装成：给定一个文档，返回其前k个出现次数最多的单词。
Given a document, return the k most frequent words. Assume punctuation are removed.
Given a non-empty array of strings, return the k most frequent elements. - 如果写出了桶排序，可以考虑假设机器memory有限，只够O(m)，不能一次性读出整个文档，也就是不能用桶排序，只能用堆选择。
- 如果写出了堆选择，可以考虑k比较大，如果进一步提高时间复杂度，也就是只能O(n),符合这个要求就只有计数排序，基数排序和桶排序。
这是priorityQueue实现的Heap（对于基本数据类型默认是最小堆，但由于Node是自定义，必须实现Comparator），由于PQ需要额外空间，所以
较少用。
Java代码：
1 | public List<Integer> topKFrequent3(int[] nums, int k) { |
