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;
}
``````
Categories: Algorithm

Article Rating
Subscribe
Notify of