347

class Solution {
public:
    vector<int> num;
    unordered_map<int, int> freq;

    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto n: nums){
            freq[n]++;
            if(freq[n] == 1) num.push_back(n);
        }
        int kn = num.size()-k;
        quickselect(0, num.size()-1, kn);
        vector<int> ans;
        while(k--){
            ans.push_back(num.back());
            num.pop_back();
        }
        return ans;
    }

    void quickselect(int left, int right, int k){
        if(left == right) return;
        int pivot = partition(left, right);
        if(k == pivot)
            return;
        else if(k < pivot)
            quickselect(left, pivot-1, k);
        else
            quickselect(pivot+1, right, k);
    }

    int partition(int left, int right){
        int pivot = left;
        while(left <= right){
            while(left <= right && freq[num[left]] <= freq[num[pivot]])
                left++;
            while(left <= right && freq[num[right]] > freq[num[pivot]])
                right--;
            if(left < right)
                swap(num[left], num[right]);
            else
                swap(num[pivot], num[right]);
        }
        return right;
    }

};