C++ Exercises: Bucket Sort

Exercises: Top K Frequent Elements

Given an array of integers named nums, and a number named k.
Find the first K of the highest frequency numbers.
You can show the answers in any order.

Input: nums = [1, 1, 1, 1, 2, 4, 2, 3], k = 2
Ouput: [1,2]

Analysis:
nums = [1, 1, 1, 1, 2, 4, 2, 3], k = 2
value – count:
1 ~ 4
2 ~ 2
4 ~ 1
3 ~ 1

count – value:
4 ~ 1
2 ~ 2
1 ~ 4, 3

Sort all numbers by their counts and display the numbers one by one. These count sets look like different buckets.

#include <iostream>
#include <iostream>
#include <functional>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int maxCount = 0;
        // value: times
        for( auto element: nums )
        {
            maxCount = max( maxCount, ++count[element] );
        }
        // times : value1, value2, value3 ...
        vector<vector<int>> backet;
        for( int i = 0; i <= maxCount; ++i ){
            backet.push_back(vector<int>{});
        }
        for( auto element: count )
        {
            backet[element.second].push_back( element.first );
        }

        vector<int> ans;
        int times = 0;
        for( int i = maxCount; i > 0 && ans.size() < k; --i )
        {
            for( auto value: backet[i] )
            {
                ans.push_back( value );
                if( ans.size() >= k ) break;
            }
        }   
        return ans;
    }
};

int main()
{
    vector<int> nums{1,1,1,1,2,4,2,3};
    int k = 2;

    Solution worker;
    auto ans = worker.topKFrequent( nums, k );
    for( auto element: ans )
    {
        cout << element << " ";
    }
    cout << endl;
    return 0;
}

Exercises: Sort Characters By Frequency

The problem is similar to Top K Frequent Elements.
Note: ans += charMap[i][j]; is more efficient than ans = ans + charMap[i][j];

#include <iostream>
#include <iostream>
#include <functional>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> count; //value - count
        for( int i = 0; i < s.size(); ++i ){
            ++count[s[i]];
        }
        vector<char> charMap[s.length()+1];
        // count - value
        for( auto element: count )
        {
            charMap[element.second].push_back( element.first );
        }

        string ans;
        for(int i = s.length(); i >= 1; --i)
        //for(int i = 1; i < charMap.size(); i++)
        {
            for( int j = 0; j < charMap[i].size(); ++j )
            {
                for( int k = 0; k < i; ++k )
                {
                    ans += charMap[i][j];
                }
            }
        }
        return ans;
    }
};

int main (int argc, const char* argv[]) {
    string str = "tree";
    Solution worker;
    auto ans = worker.frequencySort( str );
    cout << ans;

    return 0;
}

Exercises: Sort Colors

#include <iostream>
#include <iostream>
#include <functional>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<short> values[3];
        for( auto num: nums )
        {
            values[num].push_back( num );
        }
        nums.clear();
        for( int i = 0; i < 3; ++i )
        {
            for( auto value: values[i] )
            {
                nums.push_back( value );
            }
        }
    }
};

int main (int argc, const char* argv[]) {
    vector<int> numbers{ 2,0,2,1,1,0 };
    Solution worker;
    worker.sortColors( numbers );
    for ( auto num: numbers )
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}