The number of different values
n integers are given (up to 109 in absolute value, n ≤ 2·105). Print how many of them are different.
Example
Input
6
5 -2 5 1000000000 -2 7Output
4The containers set and map keep their elements ordered and allow adding, removing and finding in O(log n) time. In competitions they are used for counting occurrences, removing duplicates, tracking the smallest and the largest element and finding the nearest element while the set is changing.
set keeps every element at most once, always sorted. Adding an existing element changes nothing.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(5);
s.insert(1);
s.insert(9);
s.insert(5); // 5 already exists – nothing changes
cout << "size: " << s.size() << endl;
for (int x : s) cout << x << " "; // always increasing
cout << endl;
cout << "is 9 there? " << s.count(9) << endl; // 1 or 0
s.erase(9);
cout << "is 9 there? " << s.count(9) << endl;
cout << "smallest: " << *s.begin() << endl;
cout << "largest: " << *s.rbegin() << endl;
return 0;
}
| Operation | Meaning | Complexity |
|---|---|---|
s.insert(x) | adds x | O(log n) |
s.erase(x) | removes x | O(log n) |
s.count(x) | 1 if x exists, otherwise 0 | O(log n) |
*s.begin(), *s.rbegin() | the smallest and the largest element | O(1) |
s.lower_bound(x) | an iterator to the first element >= x | O(log n) |
s.size(), s.empty() | the number of elements, whether it is empty | O(1) |
A sorted array and lower_bound (SR) work as long as the array does not change. If elements are added between the queries, we use the set's method s.lower_bound(x). Example: parking spots are taken one by one, and for every new car we look for the first free spot with a number >= x.
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, q;
cin >> n >> q; // spots 1..n, q cars
set<int> freeSpots;
for (int i = 1; i <= n; i++) freeSpots.insert(i);
while (q--) {
int x;
cin >> x; // the driver wants spot x or the first larger one
auto it = freeSpots.lower_bound(x);
if (it == freeSpots.end()) {
cout << "none" << endl;
} else {
cout << *it << endl;
freeSpots.erase(it); // the spot is now taken
}
}
return 0;
}
multiset allows several equal elements, and it is still sorted. Watch out: ms.erase(x) removes all copies of the number x; one copy is removed through an iterator: ms.erase(ms.find(x)).
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {4, 1, 4, 7, 4};
cout << "fours: " << ms.count(4) << endl;
ms.erase(ms.find(4)); // removes only one four
cout << "fours: " << ms.count(4) << endl;
for (int x : ms) cout << x << " ";
cout << endl;
return 0;
}
A multiset is handy when you constantly need to know the smallest and the largest of the current elements, while elements are both added and removed (for example, prices in a shop that change).
map<K, V> assigns a value to every key. The basics are described in the lesson Data dictionary – maps in C++; here the most important use is counting occurrences when the values are too large for an ordinary array of counters (up to 109, negative, or words).
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
map<string, int> count; // word -> number of occurrences
for (int i = 0; i < n; i++) {
string word;
cin >> word;
count[word]++; // a new word automatically gets 0, and then it is increased
}
for (auto &entry : count) // the keys are sorted alphabetically
cout << entry.first << " " << entry.second << endl;
return 0;
}
count[x] for a key that does not exist adds it with the value 0. To check whether a key exists, use count.count(x).The versions without ordering use a hash table: adding and finding are O(1) on average, but the elements are not sorted and there is no lower_bound. They are used when the order does not matter and there are many operations.
| set / map | unordered_set / unordered_map | vector + sort | |
|---|---|---|---|
| Finding | O(log n) | O(1) on average | O(log n) (binary search) |
| Adding while working | O(log n) | O(1) on average | slow (O(n)) |
| Sorted order | yes | no | yes |
| The nearest element | yes (lower_bound) | no | yes |
| When | a dynamic set, ordering | only counting / existence | the data do not change |
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
n integers are given (up to 109 in absolute value, n ≤ 2·105). Print how many of them are different.
6
5 -2 5 1000000000 -2 74n words are given. Print the word that appears the most times and the number of its occurrences; if there are several, print the alphabetically first one.
7
cat dog cat bird dog cat fishcat 34
b a b aa 2Changes happen in a shop. The query + x adds a product with the price x, the query - x removes one product with the price x (it certainly exists), and the query ? asks to print the lowest and the highest current price (or empty).
7
+ 5
+ 3
+ 5
?
- 3
- 5
?3 5
5 5set does not keep duplicates; if you need them, use multiset.ms.erase(x) removes all copies, ms.erase(ms.find(x)) only one.lower_bound(s.begin(), s.end(), x) on a set – that is O(n). The correct form is s.lower_bound(x).*it) check that it is not end().1. How many elements does a set have after insert(3), insert(3), insert(5)?
2. What is the complexity of adding to a set?
3. What happens when you read count["x"] for a key that does not exist in the map count?
4. How do you remove only one copy of the number x from a multiset?