347. 前 K 個(gè)高頻元素

難度中等

1610

給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，請(qǐng)你返回其中出現(xiàn)頻率前?k?高的元素。你可以按?任意順序?返回答案。

?

示例 1:

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

示例 2:

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

?

提示：

• 1 <= nums.length <= 105

• k?的取值范圍是?[1, 數(shù)組中不相同的元素的個(gè)數(shù)]

• 題目數(shù)據(jù)保證答案唯一，換句話說，數(shù)組中前?k?個(gè)高頻元素的集合是唯一的

?

進(jìn)階：你所設(shè)計(jì)算法的時(shí)間復(fù)雜度?必須?優(yōu)于?O(n log n)?，其中?n?是數(shù)組大小

代碼：

class?Solution?{

public:

????class?com{

????public:

????????bool?operator()(const?pair<int,int>&?x,const?pair<int,int>&?y){

????????????return?x.second?>?y.second;

????????}

????};

????vector<int>?topKFrequent(vector<int>&?nums,?int?k)?{

????????unordered_map<int,int>?vec1;

????????for(int?i=0;i<nums.size();i++){

????????????vec1[nums[i]]++;

????????}

????????priority_queue<pair<int,int>,vector<pair<int,int>>,com>?que;

????????for(unordered_map<int,int>::iterator?it?=?vec1.begin();it?!=?vec1.end();it++){

????????????que.push(*it);

????????????if(que.size()>k)que.pop();

????????}

????????vector<int>?ans(k);

????????for(int?i=k-1;i>=0;i--){

????????????ans[i]?=?que.top().first;

????????????que.pop();

????????}

????????return?ans;

????}

};