Algorytmy i struktury danych · Middle · Pytanie 63 z 75
Każda liczba w tablicy występuje dwa razy oprócz jednej. Jak ją znaleźć w czasie O(n) i z O(1) pamięci?
- 1Policzyć wystąpienia każdej liczby w mapie
- ✓Poprawna odpowiedź: XOR wszystkich liczb: pary się znoszą, zostaje pojedyncza
- 3Posortować tablicę i porównać sąsiednie wartości
Wyjaśnienie
a ^ a = 0 i a ^ 0 = a, a XOR jest przemienny, więc pary znikają w dowolnej kolejności. Sortowanie to O(n log n); mapa to O(n) czasu, ale O(n) pamięci.