题目描述
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
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多的的数字。
算法1
(堆) $O(nlogk)$
题解1:使用哈希表统计每个数字出现的个数,然后维护一个大小为k的小顶堆即可。
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for(auto x : nums) hash[x] ++;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
int i = 0;
for(auto &it : hash)
{
if(i < k)
{
i ++;
q.push(make_pair(it.second,it.first));
}else
{
if(it.second > q.top().first)
{
q.pop();
q.push(make_pair(it.second,it.first));
}
}
}
vector<int> res(k);
for(int i = 0 ; i < k ; i ++)
{
res[i] = q.top().second;
q.pop();
}
return res;
}
算法2
(分治) $O(n)$
因为不需要返回特定的顺序,只需要找到前K个,所以可以利用类似快速排序的思想。
class Solution {
public:
struct ele{
int val,cnt;
ele(){}
ele(int val,int cnt):val(val),cnt(cnt){}
};
vector<int> res;
void getTopK(vector<ele>& arr,int l,int r,int k)
{
if(l > r) return;
int pivot = arr[l].cnt,i = l,j = r;
while(i < j)
{
while(i < j && arr[j].cnt <= pivot) j --;
while(i < j && arr[i].cnt >= pivot) i ++;
if(i < j)
swap(arr[i],arr[j]);
}
swap(arr[i],arr[l]);
if(i - l + 1 == k)
{
for(int t = l ; t <= i ; t ++)
res.push_back(arr[t].val);
return;
}else if(i - l >= k)
getTopK(arr,l,i - 1,k);
else
{
for(int t = l ; t <= i ; t ++)
res.push_back(arr[t].val);
getTopK(arr,i + 1,r,k - (i - l + 1));
}
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for(auto x : nums) hash[x] ++;
int n = hash.size(),i = 0;
vector<ele> arr(n);
for(auto &it : hash)
arr[i ++] = ele(it.first,it.second);
getTopK(arr,0,n - 1,k);
return res;
}
};
算法3
(计数排序) $O(n)$
题解3:计数排序。我们可以先统计每个数字出现了多少次,在统计一下出现次数为t
次的元素各有多少个,然后利用计数排序的思想判断一下出现次数前K多的数字最少出现多少次,求出这个下界,最后再遍历一次哈希表,将所有出现次数大于等于这个下界的元素加入答案。因为题目中已经表明了第k
多和第k + 1
多的元素出现次数不同,这就为我们省去了很多的边界判断。
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hash;
for(auto x : nums) hash[x] ++;
int n = nums.size(),t = n,count = 0;
vector<int> cnt(n + 1,0);
for(auto &it : hash) cnt[it.second] ++;
for(;t >= 0 ; t --)
{
count += cnt[t];
if(count >= k)
break;
}
vector<int> res;
for(auto &it : hash)
if(it.second >= t)
res.push_back(it.first);
return res;
}
堆排序else那的比较没必要写,只要把小根堆堆顶删掉就行