Counting and sorting are skills we typically start training from around the age of two or three.
It's time to put those skills to good use!
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input. For each set of data, the first line contains an integer N, where 1 <= N <= 1000. Following that, there are N integers A1, A2, ..., AN ranging from 0 to 9. | Sort the input numbers in descending order of frequency of occurrence. If the frequencies are the same, output the smaller number first. Refer to the example output. |
| 5 1 4 5 1 4 10 0 0 0 0 9 9 9 2 2 8 | 1 4 5 0 9 2 8 |
Thought Process
Start by declaring a Map to record the frequency of each number.
Next, iterate over the map using a for loop (for (auto it : Map)) to access each number and its frequency. Declare a Vector<pair> ans to store these two pieces of data. Multiply it.first by -1 because we want smaller numbers to appear later in the output (we'll use descending order). This allows us to output from the end later. Swap it.first and it.second and push them back into ans. After accessing all the data, sort the ans vector. Finally, output from the last position to the first position of ans, multiplying ans[i].second by -1.
Sample Code－ZeroJudge A218: How many times?
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N)
{
map<int, int>MAP;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
MAP[tmp]++;
}
vector<pair<int, int>>ans;
for (auto it:MAP)
{
pair<int, int>tmp;
tmp.first = it.second;
tmp.second = it.first * -1;
ans.push_back(tmp);
}
sort(ans.begin(), ans.end());
for (int i = int(ans.size())-1; i>=0; i--)
{
cout << ans[i].second * -1 << " ";
}
cout << "\n";
}
}
//ZeroJudge A218
//Dr. SeanXD