O(N) using unordered_map and topk


  • 0
    A

    topk with fat partition.

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> c;
            for (int n: nums) {
                c[n] ++;
            }
            using pp=pair<int, int>;
            vector<pp> ans;
            transform(c.begin(), c.end(), back_inserter(ans), [](pp e) {
                return pp(e.second, e.first);
            });
            
            int s = 0;
            int t = ans.size();
            while (s < t) {
                int pivot = ans[s].first;
                int i = s;
                int j = s;
                int n = t-1;
                while (j<=n) {
                    if (ans[j].first > pivot) {
                        swap(ans[j], ans[i]);
                        i++;
                        j++;
                    } else if (ans[j].first < pivot) {
                        swap(ans[n], ans[j]);
                        n--;
                    } else j++;
                }
                if (i<k && (k-1)<=n) {
                    vector<int> ret;
                    for(int x=0;x<k;x++) {
                        ret.push_back(ans[x].second);
                    }
                    return ret;
                } else if (k <= i) {
                    t = i;
                } else {
                    s = n + 1;
                }
            }
            return {};
        }
    };
    

Log in to reply
 

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