2019-11-25 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解决思路

思路很清晰，就是首先必须要遍历一遍nums数组，设计一个map用来存储数组中的值和某个值存在的次数。然而map中内部结构是红黑树，key是有序的，下一步就是利用value进行排序，将映射表中的元素先转储到pair<int ,int>中，然后对其进行按值逆序排序，然后只需要再次遍历包含pair元素的数组的前k的元素，将其first值push_back到一维数组中返回。

C++1

class Solution {
public:
    static int cmp(const pair<int, int>& x, const pair<int, int>& y)  
    {  
        return x.second > y.second;  
    }  
   
    void sortMapByValue(map<int, int>& tMap,vector<pair<int, int> >& tVector)  
    {  
        for (map<int, int>::iterator curr = tMap.begin(); curr != tMap.end(); curr++)   
            tVector.push_back(make_pair(curr->first, curr->second));    
        sort(tVector.begin(), tVector.end(), cmp);  
    }  

    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> hm;
        for(int i: nums){
            if(hm.count(i)<=0){
                hm.insert(make_pair(i, 1));
            }else{
                hm[i] = hm[i]+1;
            }
        }
        vector<pair<int,int>> tVector;
        sortMapByValue(hm,tVector);
        
        
        vector<int> res;
        int c=0;
        for(int i=0;i<tVector.size();i++){
            if(c == k){
                break;
            }else{
                res.push_back(tVector[i].first);
                c++;       
            }
        }
        return res;
    }
};

参考博客

C++ 对map进行排序
c++ STL中常见容器的时间复杂度
c++ map与unordered_map区别及使用
c++中map与unordered_map的区别
C++中pair的用法