Top K Frequent Elements Solutions in C++

// Source : https://leetcode.com/problems/top-k-frequent-elements/
// Author : Calinescu Valentin
// Date   : 2016-05-02



class Solution {
public:
    struct element//structure consisting of every distinct number in the vector,
    //along with its frequency
    {
        int number, frequency;
        bool operator < (const element arg) const
        {
            return frequency < arg.frequency;
        }
    };
    priority_queue <element> sol;//we use a heap so we have all of the elements sorted
    //by their frequency
    vector <int> solution;
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 1;
        for(; i < nums.size(); i++)
        {
            int freq = 1;
            while(i < nums.size() && nums[i] == nums[i - 1])
            {
                i++;
                freq++;
            }
            element el;
            el.number = nums[i - 1];
            el.frequency = freq;
            sol.push(el);
        }
        if(i == nums.size())//if we have 1 distinct element as the last
        {
            element el;
            el.number = nums[nums.size() - 1];
            el.frequency = 1;
            sol.push(el);
        }
        while(k)//we extract the first k elements from the heap
        {
            solution.push_back(sol.top().number);
            sol.pop();
            k--;
        }
        return solution;
    }
};

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <cassert>

using namespace std;

/// Using Tree Set
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        assert(k > 0);

        unordered_map<int, int> freq;
        for(int num: nums)
            freq[num] ++;

//        cout << "freq:" << endl;
//        for(pair<int, int>p: freq)
//            cout << "v: " << p.first << " f: " << p.second << endl;
//        cout << endl;

        assert(k <= freq.size());

        set<pair<int, int>, greater<pair<int, int>>> record;
        for(pair<int, int> p: freq)
            record.insert(make_pair(p.second, p.first));

        vector<int> res;
        for(int i = 0 ; i < k ; i ++){
            set<pair<int, int>>::iterator iter = record.begin();
            advance(iter, i);
            assert(iter != record.end());
            res.push_back(iter->second);
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 1, 1, 2, 2, 3};
    print_vec(Solution().topKFrequent(nums, 2));

    return 0;
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cassert>

using namespace std;

/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {

private:
    unordered_map<int,int> freq;

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        assert(k > 0);

        freq.clear();
        for(int i = 0 ; i < nums.size() ; i ++ )
            freq[nums[i]] ++;

        assert(k <= freq.size());

        vector<int> res;
        for(pair<int, int> p: freq)
            res.push_back(p.first);

        sort(res.begin(), res.end(), [this](int a, int b){
            if(this->freq[a] != this->freq[b])
               return this->freq[a] > this->freq[b];
            return a < b;
        });

        return vector<int>(res.begin(), res.begin() + k);
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 1, 1, 2, 2, 3};
    print_vec(Solution().topKFrequent(nums, 2));

    return 0;
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cassert>

using namespace std;

/// Priority Queue
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        assert(k > 0);

        // 统计每个元素出现的频率
        unordered_map<int,int> freq;
        for(int i = 0 ; i < nums.size() ; i ++ )
            freq[nums[i]] ++;

        assert(k <= freq.size());

        // 扫描freq,维护当前出现频率最高的k个元素
        // 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        for(const pair<int, int>& p: freq){
            if(pq.size() == k && p.second > pq.top().first) pq.pop();
            if(pq.size() < k) pq.push(make_pair(p.second , p.first));
        }

        vector<int> res;
        while(!pq.empty()){
            res.push_back(pq.top().second);
            pq.pop();
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    print_vec(Solution().topKFrequent(nums1, 2));

    vector<int> nums2 = {3, 0, 1, 0};
    print_vec(Solution().topKFrequent(nums2, 1));
    // 0

    return 0;
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2020-03-13

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cassert>
#include <set>

using namespace std;

/// Priority Queue for n-k elements
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        assert(k > 0);

        // 统计每个元素出现的频率
        unordered_map<int,int> freq;
        for(int i = 0 ; i < nums.size() ; i ++ )
            freq[nums[i]] ++;

        assert(k <= freq.size());

        // 扫描freq,维护当前出现频率最低的 n - k 个元素
        // 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
        priority_queue<pair<int,int>> pq;
        for(const pair<int, int>& p: freq){
            if(freq.size() - k && pq.size() == freq.size() - k && p.second < pq.top().first) pq.pop();
            if(pq.size() < freq.size() - k) pq.push(make_pair(p.second , p.first));
        }

        set<int> not_contains;
        while(!pq.empty()){
            not_contains.insert(pq.top().second);
            pq.pop();
        }

        vector<int> res;
        for(const pair<int, int>& p: freq)
            if(!not_contains.count(p.first))
                res.push_back(p.first);
        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 1, 1, 2, 2, 3};
    print_vec(Solution().topKFrequent(nums, 2));

    return 0;
}