Что такое множество и какие проблемы оно решает?

Question

Accepted Answer

**Множество** — это неупорядоченная коллекция **уникальных** элементов. Его основная сила в том, что ответить на вопрос "находится ли X здесь?" можно в **O(1) в среднем**, и оно автоматически отклоняет дубликаты.

## Пример

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

Большинство множеств реализованы как **hash sets** (хеш-таблица, хранящая только ключи), поэтому:

| Операция | В среднем |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Распространённые применения

- **Удаление дубликатов** — удалите повторения из списка в одну строку.
- **Быстрая проверка принадлежности** — "я это видел раньше?"
- **Связи** — пересечение/объединение/разность между группами.

## Почему это важно

Множества делают "уникальность" и "принадлежность" тривиальными и быстрыми, заменяя медленные вложенные циклы по спискам.

Частая хитрость на интервью — обнаружение дубликатов или посещённых узлов — сводится к нескольким операциям над множествами.