347. Top K Frequent Elements

Total Accepted: 2605 
Total Submissions: 5933 
Difficulty: Medium
Given a non-empty array of integers, return the k most frequent elements.
For example, Given  [1,1,1,2,2,3]  and k = 2, return  [1,2] .
Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Subscribe to see which companies asked this question
Hide Tags
 
Hash Table Heap
Hide Similar Problems
 
(M) Word Frequency (M) Kth Largest Element in an Array
分析:
2つのコア操作、
1,ハッシュmapを用いて頻度とその対応数を統計する
2,周波数(およびそれに対応する数字)に基づいて最大のスタックを構築し、常にスタックのトップをポップアップして現在の最大の周波数を取得します.

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // ，     
        unordered_map<int,int> mapping;
        for(int number : nums)
            mapping[number]++;
        // ，              
        // pair<first, second>: first is frequency,  second is number
        priority_queue<pair<int,int>> pri_que; //   
        for(auto it = mapping.begin(); it != mapping.end(); it++)
            pri_que.push(make_pair(it->second, it->first));
        // ，        
        while(result.size() < k){
                result.push_back(pri_que.top().second);
                pri_que.pop();
        }
        return result;
    }
private:
    vector<int> result;
};

注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/51317106
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895