05 August 2008
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given 1
[1,1,1,2,2,3]
1
[1,2]
Note:
高频题，给一个非空的整数数组和一个总是有效的的整数k，返回前k个最多出现的元素。可以用HashMap来做桶排序，TreeMap和最大堆来做。
用最大堆，把数字和其频率放到HashMap中，然后把map的entry放到maxHeap中，从最顶上拿走k个数字的entry然后相对应的keys就是最高频率的k个数字。
时间复杂度：O(nlogk)，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，遍历用于存储元素频率的 map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这里维护堆的数目是 k，所以这一系列操作的时间复杂度是 O(nlogk) 的；因此，总的时间复杂度是 O(nlogk)。
空间复杂度：O(n)，最坏情况下（每个元素都不同），map 需要存储 n 个键值对，优先队列需要存储 k 个元素，因此，空间复杂度是 O(n)。
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 {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);//原数组的元素为key，出现次数为value
}
//利用最大堆
PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>(
(a, b) -> (b.getValue() - a.getValue())
);
maxHeap.addAll(map.entrySet());
int[] result = new int[k];
int index = 0;
while (index < k) {
Map.Entry<Integer, Integer> entry = maxHeap.poll();//取出顶部元素并删除
result[index] = entry.getKey();
index++;
}
return result;
}
}
同理，用最小堆也可以
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
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
// hashmap统计出现次数
for(int num: nums){
map.put(num, map.getOrDefault(num,0) + 1);
}
// 用最小堆准备找到k个
PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
// 遍历hashmap
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
minHeap.add(entry);
if (minHeap.size() > k) {
minHeap.poll();
}
}
// 找个k个最多出现的值
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = minHeap.poll().getKey();
}
return result;
}
}
基于快速排序，我们可以使用基于快速排序的方法，求出「出现次数数组」的前 k 大的值。
在对数组arr[l…r]做快速排序的过程中，我们首先将数组划分为两个部分arr[i…q−1]与arr[q+1…j]，并使得arr[i…q−1] 中的每一个值都不超过arr[q]，且arr[q+1…j] 中的每一个值都大于arr[q]。
于是，根据 k 与左侧子数组arr[i…q−1] 的长度（为q−i）的大小关系：
如果k≤q−i，则数组arr[l…r] 前 k 大的值，就等于子数组arr[i…q−1] 前 k 大的值。 否则，数组arr[l…r] 前 k 大的值，就等于左侧子数组全部元素，加上右侧子数组arr[q+1…j] 中前k−(q−i) 大的值。
原版的快速排序算法的平均时间复杂度为 O(NlogN)。我们的算法中，每次只需在其中的一个分支递归即可，因此算法的平均时间复杂度降为 O(N)。
时间复杂度：O(N^2)，其中 N 为数组的长度
空间复杂度：O(N)
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
36
37
38
39
40
41
42
43
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
List<int[]> values = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{num, count});
}
int[] ret = new int[k];
qsort(values, 0, values.size() - 1, ret, 0, k);
return ret;
}
public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
int picked = (int) (Math.random() * (end - start + 1)) + start;
Collections.swap(values, picked, start);
int pivot = values.get(start)[1];
int index = start;
for (int i = start + 1; i <= end; i++) {
if (values.get(i)[1] >= pivot) {
Collections.swap(values, index + 1, i);
index++;
}
}
Collections.swap(values, start, index);
if (k <= index - start) {
qsort(values, start, index - 1, ret, retIndex, k);
} else {
for (int i = start; i <= index; i++) {
ret[retIndex++] = values.get(i)[0];
}
if (k > index - start + 1) {
qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
}
}
}
}
HashMap桶排序的做法，在建立好数字和其出现次数的映射后利用桶排序取k个最频繁的数字，时空均为O(n)
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
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);//原数组的元素为key，出现次数为value
}
//创建一个放buckets的list
List<Integer>[] bucket = new List[nums.length + 1];//如果只有一个元素，那么也需要一个index为1的bucket
for (int num : map.keySet()) {
int freq = map.get(num);
if (bucket[freq] == null) {//没有这个桶，就加一个
bucket[freq] = new LinkedList<>();
}
bucket[freq].add(num);//在每个桶加上各自的元素
}
List<Integer> result = new LinkedList<>();
for (int i = bucket.length - 1; i > 0 && k > 0; i--) {//从做到右取n个
if (bucket[i] != null) {//只要出现过
List<Integer> list = bucket[i];
result.addAll(list);
k -= list.size();
}
}
return result;
}
}
利用TreeMap自动排序
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
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);//原数组的元素为key，出现次数为value
}
//利用treeMap自动排序
TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
for (int num : map.keySet()) {
int freq = map.get(num);
if (!freqMap.containsKey(freq)) {
freqMap.put(freq, new LinkedList<>());
}
freqMap.get(freq).add(num);
}
List<Integer> result = new ArrayList<>();
while (result.size() < k) {//取前k位
Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
result.addAll(entry.getValue());
}
return result;
}
}