给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
提示:
你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案
方法一:快速选择
第一次快速可将1个在基准值x右边但大于x的元素归到x的左边作为答案,k次可保证有k个
typedef pair<int, int> pii;
class Solution {
public:
vector<int> ans;
void quick_select(int l, int r, int k, vector<pii>& A) {
if (l>r) return;
if (l==r && k==1) {
ans.emplace_back(A[l].first);
return;
}
int i=l-1, j=r+1, x=A[(l+r)>>1].second;
while (i<j) {
do i++; while(A[i].second>x); //将大于x.second的数都放在左边
do j--; while(A[j].second<x);
if (i<j) swap(A[i], A[j]);
}
if (j-l+1>=k) { //左边够了k个
quick_select(l, j, k, A);
} else {
for (int p=l; p<=j; p++) ans.emplace_back(A[p].first);
quick_select(j+1, r, k-(j-l+1), A);
}
}
vector<int> topKFrequent(vector<int>& arr, int k) {
unordered_map<int, int> mp;
for (int x : arr) mp[x]++;
vector<pii> B;
for (auto p : mp) B.emplace_back(p);
quick_select(0,B.size()-1,k,B);
return ans;
}
};
复杂度分析
- Time:\(O(nlogk)\),
- Space:\(O(n)\)