cpp刷题打卡20——前k个高频元素

前k个高频元素题目描述给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。题目代码class Solution { public: class Mycompare { public: bool operator()(pairint, int v1, pairint, int v2) { return v1.second v2.second; } }; vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int map; for(int i 0; inums.size(); i){ map[nums[i]]; } vectorpairint, int ve; while(!map.empty()){ ve.push_back(*(map.begin())); map.erase(map.begin()); } sort(ve.begin(), ve.end(), Mycompare()); vectorint result(k); for(int i 0; ik; i){ result[i] ve[i].first; } return result; } };思路就是先统计每个元素出现的频次对频次从大到小排序输出前k个。统计频次的话首先就想到用map键值对的形式操作key值为元素value为其出现的频次要用unordered_map虽然map的排序是按照key值排的我们需要按照value排。接下来是从大到小排序想到sort默认sort是升序的然后就用class Mycompare改变一下其排序顺序。最后就是输出最高频次的前k个要注意我们比的是value但是最后输出的是key不要把unordered_map里面的搞混淆了。优化class Solution { public: class Mycompare { public: bool operator()(pairint, int v1, pairint, int v2) { return v1.second v2.second; } }; vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int map; for(int i 0; inums.size(); i){ map[nums[i]]; } priority_queuepairint, int, vectorpairint, int, Mycompare pri_que; for(unordered_mapint, int::iterator it map.begin(); it!map.end(); it){ pri_que.push(*it); if(pri_que.size() k){ pri_que.pop(); } } vectorint result(k); for(int i k-1; i0; i--){ result[i] pri_que.top().first; pri_que.pop(); } return result; } };用了优先级队列priority_queue由于题目中只需要前k个高频元素并不需要我们把所有的频次都进行排序也就是只排序k个元素这也正是优化之处。在默认的情况下优先级队列priority_queue是利用大顶堆完成排序的就是从大到小排我们需要的是从小到大排所以需要指定一下排列顺序。为什么这里需要从小到大排序呢我们分明是找前k个高频次的元素。这是因为我们想要只统计最大的前k个元素不想要全部都排序所以只有小顶堆能满足我们的要求当队列个数大于k个时我们就可以直接用pop弹出也就是每次将最小的元素弹出了最后留在小顶堆里的就是前k个最大元素。注意在写快排的compare函数的时候return leftright 就是从大到小return leftright就是从小到大而优先级队列的定义正好是反过来的。通过这个优化我们也从时间复杂度为O(nlogn)降到O(nlogk)。