347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

3种方法
https://leetcode.com/discuss/100713/3-ways-to-solve-this-problem

普通方法heap O(nlogn)：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(auto &i : nums)
            mp[i]++;
        priority_queue<pair<int,int>> pq;
        for(auto &i : mp) 
            pq.push(make_pair(i.second, i.first));
        vector<int> res;
        while(k-- > 0 && !pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

k selection (来自discuss) 时间复杂度是多少？O(nlogn)? :

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        if (!nums.size()) return res;
        unordered_map<int, int> cnt;
        for (auto num : nums) cnt[num]++;
        vector<pair<int, int>> num_with_cnt;
        for (auto kv : cnt) {
            num_with_cnt.push_back({kv.first, kv.second});
        }
        kselection(num_with_cnt, 0, num_with_cnt.size()-1, k);
        for (int i = 0; i < k && i < num_with_cnt.size(); ++i) {
            res.push_back(num_with_cnt[i].first);
        }
        return res;
    }

    void kselection(vector<pair<int, int>>& data, int start, int end, int k) {

        if (start >= end) return;
        auto pv = data[end];
        int i = start;
        int j = start;
        while (i < end) {
            if (data[i].second > pv.second) {
                swap(data[i++], data[j++]);
            } else {
                ++i;
            }
        }
        swap(data[j], data[end]);
        int num = j - start + 1;
        if (num == k) return;
        else if (num < k) {
            kselection(data, j + 1, end, k - num);
        } else {
            kselection(data, start, j - 1, k);
        }
    }
};

bucket sort（O(n)）:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(auto &i : nums)
            mp[i]++;
        vector<vector<int>> buckets(nums.size());
        for(auto &i : mp)
            buckets[i.second - 1].push_back(i.first);
        
        vector<int> res;
        for(int i = buckets.size() - 1; i >= 0; i--) {
            for(int j = 0; j < buckets[i].size(); j++) {
                res.push_back(buckets[i][j]);
                if(res.size() == k) return res;
            }
        }
        return res;
    }
};