leetcodeブラシ問題、まとめ、記録、メモ347

leetcode347Top K Frequent Elements
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
まずmapを使って、数字ごとに現れる回数を記録して、それから1つのmultimapを使って、数字の出現回数をキーにして、数字の値を値にして、multimapを挿入して、それからしっぽからk個取って、それでいいです.やはり簡単です.

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> mp;
		multimap<int, int> mp_o;
        for (int i = 0; i < nums.size(); ++i)
        {
            mp[nums[i]]++;
        }
        
        map<int, int>::iterator it = mp.begin();
        for (; it != mp.end(); ++it)
        {
            mp_o.insert(make_pair(it->second, it->first));
        }
        
        multimap<int, int>::iterator its = mp_o.end();
        vector<int> result;
        for (int i = 0; its != mp_o.begin() && i < k; ++i)
        {
            result.push_back((--its)->second);
        }
        
        return result;
    }
};