347. Top K Frequent Elements

  • 46.8%

https://leetcode.com/problems/top-k-frequent-elements/#/description

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

1
2
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.

方法一:

使用map,存放number和frequency,使用最大堆,存入最大堆。当堆大于一定值时,把堆的top值的相关信息存入res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}

vector<int> res;
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};

我的代码实现:

类似于leetcode 30

使用heap

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
44
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(auto num:nums)
map[num]++;
vector<pair<int, int>> v; // pair的定义学习
for(auto kv : map)
v.push_back(make_pair(kv.first, kv.second)); // 学习make_pair函数
vector<pair<int, int>> res(v.begin(), v.begin()+k);
for(int i=(k-2)/2; i>=0; i--){
miniheapify(res, i, k-1);
}
int n = v.size();
for(int i=k; i<n; i++){
if(v[i].second > res[0].second){
res[0] = v[i];
miniheapify(res, 0, k-1);
}
}
vector<int> ans;
for(auto pr: res)
ans.push_back(pr.first);
return ans;
}

void miniheapify(vector<pair<int,int>>& res, int start, int end){
if(start==end)
return;
int parent = start;
int child = 2 * parent + 1;
while(child <= end){
if(child+1 <= end && res[child+1].second < res[child].second)
child += 1;
if(res[parent].second>res[child].second){
swap(res[parent], res[child]);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
};

方法二:

先得到一个map,key为值,value为个数。然后依照value进行排序,类似于剑指offer 30题。

不同的是此处麻烦一些,要用到pair,逻辑是一样的。

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
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(auto num:nums)
map[num]++;
vector<pair<int, int>> v; // pair的定义学习
for(auto kv : map)
v.push_back(make_pair(kv.first, kv.second)); // 学习make_pair函数
int start = 0, end = v.size()-1;
int pos = partition(v, start, end);
while(pos != k-1){
if(pos > k-1)
end = pos - 1;
else
start = pos + 1;
pos = partition(v, start, end);
}
vector<int> res;
for(int i=0; i<k; i++)
res.push_back(v[i].first);
return res;
}

int partition(vector<pair<int, int>>& v, int start, int end){
if(start == end)
return start;
int pos = start - 1;
for(int i=start; i<end; i++){ // 注意:此处为start, 不是0
if(v[i].second > v[end].second)
swap(v[i], v[++pos]);
}
swap(v[end], v[++pos]);
return pos;
}
};

40ms, , 20/20, May.3rd, 2016

https://leetcode.com/discuss/100562/o-log-k-unordered_map-and-priority_queue-maxheap-solution

C++ O(n log(n-k)) unordered_map and priority_queue(maxheap) solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}

vector<int> res;
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};

https://discuss.leetcode.com/topic/44337/simple-c-solution-using-hash-table-and-bucket-sort

Simple C++ solution using hash table and bucket sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for (int num : nums)
++m[num];

vector<vector<int>> buckets(nums.size() + 1);
for (auto p : m)
buckets[p.second].push_back(p.first);

vector<int> ans;
for (int i = buckets.size() - 1; i >= 0 && ans.size() < k; --i) {
for (int num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k)
break;
}
}
return ans;
}
};

https://discuss.leetcode.com/topic/44313/3-ways-to-solve-this-problem

3 ways to solve this problem

using heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
for (auto kv : cnt) {
pq.push({kv.second, kv.first});
while (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
};

using selection algorithm

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
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if (!nums.size()) return res;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
vector<pair<int, int>> num_with_cnt;
for (auto kv : cnt) {
num_with_cnt.push_back({kv.first, kv.second});
}
kselection(num_with_cnt, 0, num_with_cnt.size()-1, k);
for (int i = 0; i < k && i < num_with_cnt.size(); ++i) {
res.push_back(num_with_cnt[i].first);
}
return res;
}

void kselection(vector<pair<int, int>>& data, int start, int end, int k) {

if (start >= end) return;
auto pv = data[end];
int i = start;
int j = start;
while (i < end) {
if (data[i].second > pv.second) {
swap(data[i++], data[j++]);
} else {
++i;
}
}
swap(data[j], data[end]);
int num = j - start + 1;
if (num == k) return;
else if (num < k) {
kselection(data, j + 1, end, k - num);
} else {
kselection(data, start, j - 1, k);
}
}
};

using bucket sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if (!nums.size()) return res;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
vector<vector<int>> bucket(nums.size() + 1);
for (auto kv : cnt) {
bucket[kv.second].push_back(kv.first);
}

for (int i = bucket.size() - 1; i >= 0; --i) {
for (int j = 0; j < bucket[i].size(); ++j){
res.push_back(bucket[i][j]);
if (res.size() == k) return res;
}
}

return res;
}
};

Mine Solution:

92ms, , May.3rd, 2016

1
2
3
class Solution(object):
def topKFrequent(self, nums, k):
return [key for key, value in collections.Counter(nums).most_common(k)]

Solution 1:

https://leetcode.com/discuss/100553/1-line-python-solution-using-counter-most_common-method

1
2
3
class Solution(object):
def topKFrequent(self, nums, k):
return [item[0] for item in collections.Counter(nums).most_common(k)]

https://discuss.leetcode.com/topic/44237/java-o-n-solution-bucket-sort

Java O(n) Solution - Bucket Sort

Idea is simple. Build a array of list to be buckets with length 1 to sort.

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;
}

https://discuss.leetcode.com/topic/48158/3-java-solution-using-array-maxheap-treemap

3 Java Solution using Array, MaxHeap, TreeMap

use an array to save numbers into different bucket whose index is the frequency

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
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

// corner case: if there is only one number in nums, we need the bucket has index 1.
List<Integer>[] bucket = new List[nums.length+1];
for(int n:map.keySet()){
int freq = map.get(n);
if(bucket[freq]==null)
bucket[freq] = new LinkedList<>();
bucket[freq].add(n);
}

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

return res;
}
}

use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
maxHeap.add(entry);
}

List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, Integer> entry = maxHeap.poll();
res.add(entry.getKey());
}
return res;
}
}

use treeMap. Use freqncy as the key so we can get all freqencies in order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

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> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
res.addAll(entry.getValue());
}
return res;
}
}
谢谢你,可爱的朋友。