网站开发有前途吗,南通优普营销网站建设,抖音代运营有风险吗,如何建设一个简单的公司网站题目
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1], k 1
输出: [1]
思路#xff1a;首先遍历整个数组#xff0c;并…题目
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1], k 1
输出: [1]
思路首先遍历整个数组并用哈希表记录每个数值出现的次数再用优先队列根据数值出现的次数进行排序构建大根堆。最后依次取k次堆顶元素
class Solution {
public:struct cmp{bool operator()(const pairint,int p1,const pairint,int p2){return p1.firstp2.first;}};vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int mNum;priority_queuepairint,int,vectorpairint,int,cmp PrioQue;vectorint ret;for(auto e:nums){mNum[e];}for(auto e:mNum){PrioQue.push({e.second,e.first});}for(int i0;ik;i){ret.push_back(PrioQue.top().second);PrioQue.pop();}return ret;}
};
时间复杂度会是Onlogn,n为nums数组大小
思路二维护一个sizek的小根堆时间复杂度会是Onlogk
在这里可以建立一个小顶堆然后遍历「出现次数数组」
如果堆的元素个数小于 k就可以直接插入堆中。 如果堆的元素个数等于 k则检查堆顶与当前出现次数的大小。如果堆顶更大说明至少有 k个数字的出现次数比当前值大故舍弃当前值否则就弹出堆顶并将当前值插入堆中。 遍历完成后堆中的元素就代表了「出现次数数组」中前 k大的值。
class Solution {
public:static bool cmp(pairint, int m, pairint, int n) {return m.second n.second;}vectorint topKFrequent(vectorint nums, int k) {unordered_mapint, int occurrences;for (auto v : nums) {occurrences[v];}// pair 的第一个元素代表数组的值第二个元素代表了该值出现的次数priority_queuepairint, int, vectorpairint, int, decltype(cmp) q(cmp);for (auto [num, count] : occurrences) {if (q.size() k) {if (q.top().second count) {q.pop();q.emplace(num, count);}} else {q.emplace(num, count);}}vectorint ret;while (!q.empty()) {ret.emplace_back(q.top().first);q.pop();}return ret;}
};优先级队列自定义排序
c优先队列priority_queue自定义比较函数_c priority_queue自定义比较函数_菊头蝙蝠的博客-CSDN博客 在写题时用了lambda表达式定义priority_deque第三个参数但会报错本人的错误写法
auto cmp[](vectorinta,vectorintb)-bool{return a[0]b[0];};
priority_queuevectorint,vectorvectorint,cmp q;//小顶堆
后来查了其他资料发现写法有误正确写法如下
auto cmp[](vectorinta,vectorintb)-bool{return a[0]b[0];};
priority_queuevectorint,vectorvectorint,decltype(cmp) q(cmp);//小顶堆以后还是直接用struct重载函数吧。
