Znajdź element niepowtarzających w posortowanej tablicy

Question

Źródło: Microsoft pytanie wywiad

Biorąc posortowaną tablicę, w której każdy element jest dwukrotnie występuje z wyjątkiem jednego, który jest obecny jeden raz, musimy znaleźć ten element .

Teraz standardem O (n) rozwiązaniem jest zrobić XOR z listy, która będzie zwracać element niepowtarzających (ponieważ wszystkie zduplikowane elementy znoszą się.)

Czy możliwe jest szybsze, jeśli wiemy rozwiązać ten problem tablica jest posortowana?

Answer 1

Tak, możesz użyć sortowania, aby zmniejszyć złożoność do O(log n), wykonując wyszukiwanie binarne.

Ponieważ tablica jest posortowana, przed brakującym elementem, każda wartość zajmuje plamy 2*k i 2*k+1 w tablicy (przy założeniu indeksowania opartego na 0).

więc udać się do środkowej części tablicy, powiedzmy indeksu h i sprawdzić zarówno indeks h+1 jeśli h jest parzysta, czy h-1 jeśli h jest nieparzysta. Jeśli brakujący element pojawi się później, wartości na tych pozycjach są równe, jeśli występują wcześniej, wartości są różne. Powtarzaj aż do znalezienia brakującego elementu.

Answer 2

Wykonaj binarne "wyszukiwanie" (raczej traversal) w tablicy, sprawdź oba sąsiadów, jeśli oba są różne od wartości w środku, masz rozwiązanie. To jest O(log n).