Czym jest zbiór i jakie problemy rozwiązuje?

Question

Accepted Answer

Zbiór (**set**) to **nieuporządkowana** kolekcja **unikalnych** elementów. Jego podstawowa moc to odpowiadanie na pytanie "czy X jest tutaj?" w **średnio O(1)**, a także automatyczne odrzucanie duplikatów.

## Przykład

```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}
```

Większość zbiorów jest implementowana jako **hash sets** (tablica haszująca przechowująca tylko klucze), zatem:

| Operacja | Średnio |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Popularne zastosowania

- **Deduplikacja** — usuń duplikaty z listy w jednej linii.
- **Szybkie sprawdzenie członkostwa** — "czy widziałem to wcześniej?"
- **Relacje** — przecięcie/suma/różnica między grupami.

## Dlaczego to ważne

Zbiory sprawiają, że "unikatowość" i "członkostwo" są trywialne i szybkie, zastępując wolne zagnieżdżone pętle na listach.

Typowa sztuczka egzaminacyjna — wykrywanie duplikatów lub odwiedzonych węzłów — sprowadza się do kilku operacji na zbiorach.