Wyszukiwanie pojedynczego numeru na liście [duplikat]

Nawiasem mówiąc, możesz rozwinąć ten pomysł, aby bardzo szybko znaleźć dwie unikalne liczby wśród listy duplikatów.

Nazwijmy unikalne liczby a i B. najpierw weźmy XOR wszystkiego, jak zasugerował Kyle. To co dostajemy to a^b. znamy a^b != 0, od a != b. Wybierz dowolny 1 bit A^B i użyj go jako maski -- bardziej szczegółowo: wybierz X jako potęgę 2, aby x & (A^B) było niezerowe.

Teraz podziel listę na dwie podlisty-jedna podlista zawiera wszystkie liczby y z y & x = = 0, a reszta idzie do drugiej sublisty. Przy okazji wybraliśmy x, wiemy, że a i b są w różnych wiadrach. Wiemy również, że każda para duplikatów jest nadal w tym samym wiadrze. Możemy więc teraz zastosować starą sztuczkę "XOR-em-all" do każdego wiadra niezależnie i odkryć, czym są a i B.

Bam.

O (N) czas, O (N) pamięć

HT = tabela Hash

HT.Wyczyść() przejrzyj listę w kolejności dla każdego elementu widzisz

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

Na końcu pozycja w HT jest pozycją, której szukasz.

Uwaga (credit @ Jared Updike): ten system znajdzie wszystkie nieparzyste instancje przedmiotów.

Komentarz: nie widze jak mozna glosowac na rozwiazania dajace nlogn wydajnosc. w którym wszechświecie jest to "lepsze"? Jeszcze bardziej jestem w szoku, że naznaczyłeś przyjęta odpowiedź s rozwiązanie NLogN...

Zgadzam się jednak, że jeśli wymagana jest stała pamięć, to NLogN byłby (jak dotąd) najlepszym rozwiązaniem.

Rozwiązanie Kyle ' a oczywiście nie łapie sytuacji, gdyby zestaw danych nie przestrzegał zasad. Gdyby wszystkie liczby były w parach, algorytm dałby wynik zera, dokładnie taką samą wartość, jak gdyby zero było jedyną wartością z pojedynczym occurance.

Jeśli istnieje wiele pojedynczych wartości occurance lub potrójnych, wynikiem będzie również errouness.

Testowanie zbioru danych może skończyć się bardziej kosztownym algorytmem, zarówno w pamięci, jak i w czasie.

Rozwiązanie Csmba wyświetla pewne dane o błędach (brak lub więcej niż jedna pojedyncza wartość wystąpienia), ale nie inne (czworościany). Jeśli chodzi o jego rozwiązanie, w zależności od implementacji HT, albo pamięć i/lub czas jest większy niż O(n).

Jeśli nie możemy być pewni poprawności zestawu danych wejściowych, sortowanie i zliczanie lub użycie Hashtable liczenia zdarzeń z liczbą całkowitą będącą kluczem hash byłoby wykonalne.

Powiedziałbym, że użycie algorytmu sortowania, a następnie przejście przez posortowaną listę, aby znaleźć numer, jest dobrym sposobem na to.

I teraz problem polega na znalezieniu "najlepszego" algorytmu sortowania. Istnieje wiele algorytmów sortowania, każdy z nich ma swoje mocne i słabe punkty, więc jest to dość skomplikowane pytanie. Wpis w Wikipedii wydaje się miłym źródłem informacji na ten temat.

Implementacja w Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Musisz sprecyzować, co masz na myśli przez "najlepszy" - dla niektórych liczy się tylko szybkość i kwalifikuje odpowiedź jako "najlepszy" - dla innych mogą wybaczyć kilkaset milisekund, jeśli rozwiązanie byłoby bardziej czytelne.

"najlepsze" jest subiektywne, chyba że jesteś bardziej konkretny.

That said:

Iteruj przez liczby, dla każdej liczby przeszukaj listę dla tej liczby i gdy osiągniesz liczbę, która zwraca tylko 1 dla liczby wyników wyszukiwania, jesteś załatwione.

Wygląda na to, że najlepsze, co możesz zrobić, to przejrzeć listę, dla każdego elementu Dodaj ją do listy "widzianych" lub usuń ją z" widzianych", jeśli już tam jest, a na końcu lista" widzianych " elementów będzie zawierać pojedynczy element. Jest to O (n) w odniesieniu do czasu i n w odniesieniu do przestrzeni (w najgorszym przypadku będzie znacznie lepiej, jeśli lista zostanie posortowana).

Fakt, że są liczbami całkowitymi nie ma znaczenia, ponieważ nie ma nic specjalnego, co można zrobić z / align = "left" / .. naprawdę?

Pytanie

Nie rozumiem, dlaczego wybrana odpowiedź jest "najlepsza" według jakiegokolwiek standardu. O (N*lgN) > O (N) i zmienia listę (lub tworzy jej kopię, która jest jeszcze droższa w przestrzeni i czasie). Coś przeoczyłem?

Zależy od tego, jak duże/małe/zróżnicowane są liczby. Można zastosować sortowanie radix, które znacznie skraca czas sortowania roztworu O (n log N).

Metoda sortowania i metoda XOR mają tę samą złożoność czasową. Metoda XOR jest tylko O (n), jeśli założysz, że bitowy XOR dwóch łańcuchów jest operacją w czasie stałym. Jest to równoznaczne ze stwierdzeniem, że wielkość liczb całkowitych w tablicy jest ograniczona stałą. W takim przypadku możesz użyć Radix sort do sortowania tablicy w O (n).

Jeśli liczby nie są ograniczone, to bitowy XOR zajmuje Czas O (k), gdzie k jest długością ciągu bitowego, a metoda XOR przyjmuje O (nk). Teraz ponownie Radix sort posortuje tablicę w czasie O (nk).

Można po prostu umieścić elementy w zestawie w hash, dopóki nie znajdziesz kolizji. W ruby jest to jednoliniowy.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

Więc, find_dupe([1,2,3,4,5,1]) zwróci 1.

To jest w rzeczywistości powszechne "trick" wywiad pytanie chociaż. Zwykle chodzi o listę kolejnych liczb całkowitych z jednym duplikatem. W tym przypadku ankieter często szuka, aby użyć Sumy Gaussa n - liczb całkowitych, np. n*(n+1)/2 odejmowanej od sumy rzeczywistej. Odpowiedź podręcznika to coś w tym stylu.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end