The most frequent grade
n grades from 1 to 5 are given (1 ≤ n ≤ 106). Print the grade that appears the most times; if there are several, the smallest of them.
Example
Input
8
4 5 3 4 5 4 2 5Output
4When the values of the elements are small integers (for example grades 1–5 or numbers from 0 to a million), an array can be sorted without a single comparison: we count how many times each value appears and print them in order. This runs in time O(n + K), where K is the largest value.
For the array 3 1 4 1 0 3 3 with values from 0 to 4 we make an array of counters cnt, where cnt[v] is the number of occurrences of the value v:
| v | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| cnt[v] | 1 | 2 | 0 | 3 | 1 |
We get the sorted array when we print the value 0 once, 1 twice, 2 not at all, 3 three times and 4 once: 0 1 1 3 3 3 4.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int K = 1000000; // the largest possible value
int n;
cin >> n;
vector<int> cnt(K + 1, 0); // cnt[v] = how many times v appears
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
for (int v = 0; v <= K; v++) // we print the values in order
for (int k = 0; k < cnt[v]; k++)
cout << v << " ";
cout << "\n";
return 0;
}
The algorithm goes once through the array (n steps) and once through all the possible values (K steps). It is worth it when K is not much larger than n, and it cannot be used for real numbers or for values up to 109 (the array of counters would be too large).
| Situation | Counting? |
|---|---|
| 106 grades from 1 to 5 | yes – ideal |
| 105 numbers from 0 to 106 | yes |
| 1000 numbers up to 109 | no – use sort |
| negative numbers from −1000 to 1000 | yes, with an offset: cnt[x + 1000]++ |
The same array of counters is often the goal of the task: the most frequent value, the number of different values, whether some value repeats – everything is read from cnt.
When we sort whole records (for example students by grade), we must not just print the grades. Then from the counters we calculate the starting position of every value (prefix sums – see prefix sums) and copy the records in order to their places. The order of the students with the same grade stays the same – the sort is stable.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> name(n);
vector<int> grade(n);
for (int i = 0; i < n; i++) cin >> name[i] >> grade[i];
vector<int> start(7, 0); // grades 1..5
for (int i = 0; i < n; i++) start[grade[i] + 1]++;
for (int v = 1; v <= 6; v++) start[v] += start[v - 1]; // start[v] = the first position for the grade v
vector<string> result(n);
for (int i = 0; i < n; i++) result[start[grade[i]]++] = name[i];
for (auto &s : result) cout << s << " ";
cout << endl;
return 0;
}
5
Anna 4
Mark 5
John 3
Mia 4
Peter 3John Peter Anna Mia MarkJohn comes before Peter and Anna before Mia, just as in the input – that is what stability means.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
n grades from 1 to 5 are given (1 ≤ n ≤ 106). Print the grade that appears the most times; if there are several, the smallest of them.
8
4 5 3 4 5 4 2 54n numbers from 1 to 106 are given. Print the first number (looking from the left) that has already appeared earlier in the array, or NONE.
6
7 3 9 3 7 133
1 2 3NONEK + 1 elements (indexes from 0 to K).vector or a global array, not as a local array in main (the stack is small).cnt[x + M]).1. What is the complexity of counting sort for n elements with values from 0 to K?
2. For which input is counting sort NOT suitable?
3. How many comparisons of two elements does this algorithm make?