题目描述

Given a non-empty array of integers, return the k most frequent elements.

 

题目大意

寻找数组中出现频率最高的前k个数字。

 

示例

E1

E2

 

解题思路

LeetCode@sxycwzwzq主要思想是利用priority_queue保存数字以及其次数出现的频率，由于priority_queue能将存储类型按序排列，因此可以依次入队列，当队列中的数字内容多于unique number - k时，将队列顶部的元素存储。

 

复杂度分析

时间复杂度：O(N * log(N - K))

空间复杂度：O(N)

 

代码

class Solution {public:    vector
     
       topKFrequent(vector
      
       & nums, int k) {        map
       
         unum;        // 记录不同数字的出现频率        for(int n : nums)            unum[n]++;                int thre = unum.size() - k;        vector
        
          res;        priority_queue
         
          
            > ves; for(auto it = unum.begin(); it != unum.end(); ++it) { // 将数字的频率以及该数字入队列，注意pair的顺序 ves.push(make_pair(it->second, it->first)); // 若队列的数量多余thre，表示新加入的数字出现的频率较高 if(ves.size() > thre) { res.push_back(ves.top().second); ves.pop(); } } return res; }};