Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution Approach

Expected Time complexity: $O(n*log(n))$

Click - to see solution code

C++

class Solution {
   public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        map<int, int> mp;
        vector<pair<int, int>> distinct;
        for (int i = 0; i < n; i++) {
            mp[nums[i]]++;
        }

        for (auto i : mp) {
            distinct.push_back(make_pair(i.second, i.first));
        }

        sort(distinct.begin(), distinct.end());
        reverse(distinct.begin(), distinct.end());
        vector<int> ans;
        for (int i = 0; i < k; i++) {
            ans.push_back(distinct[i].second);
        }
        return ans;
    }
};