10. Уникальные посетители
Множество HashSet<T>
Что хранит. Хранит разные значения: каждый элемент присутствует не более одного раза. Порядок элементов не гарантирован.
Для чего используют. Подходит для уникальных посетителей, списка допуска и проверки, встречался ли идентификатор раньше.
Основные операции
| Запись на C# | Назначение |
|---|
s.Add(x) | Добавить x; true, если добавлен новый элемент, иначе false. |
s.Contains(x) | Проверить наличие x. |
s.Remove(x) | Удалить x; false, если элемента не было. |
s.Count | Число разных элементов. |
foreach (int x in s) | Перебрать элементы без гарантии порядка. |
Пример
Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.
HashSet<int> ids = new HashSet<int>();
ids.Add(7);
ids.Add(9);
ids.Add(7); // Повтор не создаёт новый элемент.
Console.WriteLine(ids.Count);
Console.WriteLine(ids.Contains(9));
ids.Remove(9);
Console.WriteLine(ids.Contains(9));
Вывод:
2
True
False
Важно. Множество не хранит количество повторений и не предоставляет доступ по индексу. Для вывода по возрастанию создайте List<int> из множества и вызовите Sort().
Для этой задачи
- Запрос. Contains не добавляет идентификатор и не меняет число разных посетителей.
В журнале посещений один пользователь может встречаться много раз. Найдите число разных пользователей. Затем для каждого указанного идентификатора определите, есть ли он в исходном журнале. Запросы журнал не меняют.
Входные данные
Первая строка содержит n и q. Вторая — n идентификаторов посетителей; при n = 0 она пустая. Затем идут q строк с одним идентификатором для запроса.
Выходные данные
В первой строке выведите число разных посетителей. Для каждого запроса выведите YES, если пользователь встречался, иначе NO.
Не выводите приглашения к вводу и пояснения. Служебные слова в ответах пишите в указанном регистре.
Ограничения
0 ≤ n, q ≤ 100000; идентификаторы от 1 до 10⁹.
| № | Входные данные | Выходные данные |
|
1
|
6 4
7 9 7 11 9 7
7
8
11
8
|
3
YES
NO
YES
NO
|
|
2
|
0 2
1
1
|
0
NO
NO
|
Напишите программу
Auto