Biorąc pod uwagę, że to liczby całkowite takie, że dla wszystkich oraz występowanie każdego liczba z wyjątkiem określonej liczby w jest liczbą nieparzystą. Spróbuj znaleźć numer, którego wystąpienie jest liczbą parzystą.
Istnieje algorytm : sortujemy na i na wiele części, których wartość elementów to to samo, dlatego możemy policzyć występowanie każdego elementu.
Chcę znaleźć najgorszy przypadek - -czas-i- -przestrzeń.
Załóżmy, że i , dlatego sortowanie radix jest niedopuszczalne. Binarne operacje bitowe są dopuszczalne, na przykład .
algorithms
search-algorithms
Yai0Phah
źródło
źródło
Odpowiedzi:
Oto pomysł na prosty algorytm; po prostu policz wszystkie wystąpienia!
Podsumowując, daje to algorytm czasu liniowego, który może wykorzystywać (w sensie alokacji) dużo pamięci. Zauważ, że kluczowa jest tutaj możliwość losowego dostępu do w stałym czasie niezależnie od .C m
Dodatkowe związane z przestrzenią jest trudniejsze przy takim podejściu; Nie znam żadnej struktury danych słownikowej, która oferuje wyszukiwanie czasu . Możesz użyć tablic skrótów, dla których tutaj są implementacje z oczekiwanym czasem wyszukiwania ( rozmiar tabeli, liczba przechowywanych elementów), dzięki czemu można uzyskać dowolnie dobrą przestrzeń liniową - w oczekiwaniu. Jeśli wszystkie wartości w mapie odwzorowują tę samą wartość skrótu, zostaniesz wkręcony.O(n) O(1) O(1+k/n) n k A
źródło
Niemal trywialnym rozwiązaniem - które wykorzystuje jednak przestrzeń - jest użycie mapy skrótu. Przypomnij sobie, że mapa haszowa zamortyzowała środowisko uruchomieniowe do dodawania i wyszukiwania elementów.Θ(n) O(1)
Dlatego możemy zastosować następujący algorytm:
Przeznaczyć hash mapę . Iteracyjnego . Dla każdego elementu zwiększ liczbę zaobserwowanych wystąpień, tj. .H A i∈A H(i)++
Iteruj przez zestaw kluczy mapy skrótów i sprawdź, który z kluczy ma parzystą liczbę wystąpień.
Teraz jest to prosty algorytm, który tak naprawdę nie używa żadnej dużej sztuczki, ale czasami nawet to wystarcza. Jeśli nie, możesz sprecyzować, jakie ograniczenia przestrzeni nakładasz.
źródło