C++ O(n) Solution, use unordered_map and quick selection. Beat 98%


  • 1
    O
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> map;
            for (int num : nums)
                map[num]++;
            vector<pair<int, int>> occurrence(map.size());
            int i = 0;
            for (auto entry : map)
                occurrence[i++] = {entry.first, entry.second};
            nth_element(occurrence.begin(), occurrence.begin() + k - 1, occurrence.end(),
                        [](pair<int, int> p1, pair<int, int> p2) { return p1.second > p2.second; });
            vector<int> ans(k);
            for (int i = 0; i < k; i++)
                ans[i] = occurrence[i].first;
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.