Pytanie Znajdowanie pojedynczego numeru na liście [duplikat]


To pytanie już zawiera odpowiedź:

Jaki byłby najlepszy algorytm do znalezienia liczby, która występuje tylko raz na liście, która ma dokładnie wszystkie dwa numery dokładnie dwa razy.

Tak więc na liście liczb całkowitych (pozwala przyjąć ją jako tablicę) każda liczba całkowita powtarza się dokładnie dwa razy, z wyjątkiem jednego. Aby znaleźć ten, jaki jest najlepszy algorytm.


37
2017-08-29 20:03


pochodzenie




Odpowiedzi:


Najszybszy (O (n)) i najbardziej efektywny pod względem pamięci sposób (O (1)) to operacja XOR.

W C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

To drukuje "1", który jest jedynym, który występuje raz.

Działa to, ponieważ za pierwszym razem, gdy trafisz numer, oznacza on num zmienną samą w sobie, a po raz drugi odznacza num samą siebie (mniej więcej). Jedynym, który pozostaje nieoznakowany, jest twój duplikat.


134
2017-08-29 20:43



jest to "najlepsze" rozwiązanie, o ile faktycznie można je uporządkować. Oznacza to, że zależy to od typu danych. Nie jestem pewien, czy możesz to zrobić, czy nie, jeśli elementy są ciągami. oczywiście w tym przypadku można go rozwiązać jeszcze jedną warstwą abstrakcji ... - csmba
Istnieją sposoby na ciągi XORing poprzez XORing poszczególnych znaków - po prostu musisz mieć zmienną tymczasową tak dużą, jak największy ciąg. To, co by nie działało, to próbowanie XOR połączonej listy lub innej skomplikowanej struktury danych, ale ten problem dotyczy po prostu liczb całkowitych. - Kyle Cronin
Sprytne rozwiązanie, ale myślę, że ujemne liczby mogą trochę go zepsuć. Możesz potencjalnie użyć XOR w masce, która całkowicie odrzuci resztę twoich efektów maskowania. - Daniel Spiewak
Liczba ujemna to bitfield, podobnie jak liczba dodatnia. XOR nie dba o to - Airsource Ltd
@NickJohnson: To, czego potrzebujesz, to nie to, że hash jest "bezpieczny kryptograficznie", ale że jest "idealny" lub "dwukierunkowy" lub "unikalny". Musisz niezawodnie odzyskać obiekt z hasza. - Thomas Ahle


Przy okazji, możesz rozwinąć ten pomysł, aby bardzo szybko go znaleźć dwa unikalne liczby na liście duplikatów.

Nazwijmy unikalne liczby a i b. Najpierw weź XOR wszystkiego, jak sugerował Kyle. To, co otrzymamy, to ^ b. Znamy ^ b! = 0, ponieważ 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 przechodzi na drugą podlistę. Przy okazji wybraliśmy x, wiemy, że aib są w różnych wiaderkach. Wiemy również, że każda para duplikatów nadal znajduje się w tym samym segmencie. Możemy teraz zastosować każdą starą sztuczkę "XOR-em-all" do każdego kubełka i odkryć, co to jest a i b.

Bam.


16
2017-08-29 21:31



Kocham to . Jeśli będzie super pomocna, jeśli wszystkie pytania związane są z takim rodzajem ekspansji. - wanghq


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

HT = Tabela skrótu

HT.clear () przejrzyj listę w kolejności dla każdego przedmiotu, który widzisz

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

na końcu pozycja w HT to przedmiot, którego szukasz.

Note (credit @Jared Updike): Ten system odnajdzie wszystkie nieparzyste instancje przedmiotów.


komentarz: Nie widzę, jak ludzie mogą głosować na rozwiązania, które zapewniają wydajność NLogN. w którym wszechświecie jest "lepszy"? Jestem jeszcze bardziej zszokowany, gdy oznaczyłeś zaakceptowane rozwiązanie jako rozwiązanie NLogN ...

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


9
2017-08-29 20:08



Nie widzę teraz akceptowanej odpowiedzi, zastanawiam się, jak to się nie udało. Nawiasem mówiąc, zaznaczyłbym zaakceptowaną odpowiedź na podstawie odpowiedzi dostępnych w tym czasie. Również przyjęty nie znaczy Najlepszy :) - Vaibhav
Twoja też nie jest taka wspaniała: wykorzystuje pamięć O (n). - user9282
spójrz na pierwszą linię, pogrubioną: Mówię wprost, że jest to czas O (N), O (N), więc nie krytykujesz mojej sugestii za coś, czego już nie wskazałem. - csmba
Myślę, że musiałeś rozwinąć hash table implementacja jako algorytm, ponieważ twórca pytania zapytał o algorytm, a nie o najlepszą strukturę danych. - rook


Rozwiązanie Kyle'a oczywiście nie złapałoby sytuacji, gdyby zestaw danych nie przestrzegał zasad. Gdyby wszystkie liczby były parami, algorytm dałby wynik zerowy, dokładnie taką samą wartość, jak gdyby zero było jedyną wartością przy pojedynczym wystąpieniu.

Gdyby istniało wiele pojedynczych wartości lub trzykrotnie, wynik byłby również błędny.

Testowanie zestawu danych może zakończyć się bardziej kosztownym algorytmem, w pamięci lub czasie.

Rozwiązanie Csmba pokazuje niektóre dane errouness (brak lub więcej niż jedną wartość zdarzenia), ale nie inne (kwadratury). Co się tyczy jego rozwiązania, w zależności od implementacji HT, pamięć i / lub czas to więcej niż O (n).

Jeśli nie możemy mieć pewności co do poprawności zestawu wejściowego, sortowanie i liczenie lub użycie obliczeń z funkcją hashtable z całkowitą samą wartością będącą kluczem mieszającym byłoby wykonalne.


4
2017-09-03 13:14



@malach Propozycja Kyle'a rozwiązuje dokładnie to, co mówi problem. Nie ma sensu pisać rozwiązania O (nlogn), które chroni przed nieważnymi danymi, jeśli istnieje rozwiązanie O (n), a instrukcja problemu nie wspomina o możliwości, że dane są błędne. Tak czy owak, oto jeden artykuł, który wyjaśnia nieco więcej słów z punktu widzenia teorii informacji: sysexpand.com/?path=exercises/number-appearing-once-in-array - Zoran Horvat


Powiedziałbym, że używanie algorytmu sortowania, a następnie przeglądanie posortowanej listy w celu znalezienia numeru jest dobrym sposobem na zrobienie tego.

A teraz problemem jest znalezienie "najlepszego" algorytmu sortowania. Istnieje wiele algorytmów sortowania, z których każdy ma silne i słabe strony, więc jest to dość skomplikowane pytanie. The Wpis Wikipedii wydaje się być miłym źródłem informacji na ten temat.


1
2017-08-29 20:11





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

1
2017-09-14 15:17





Musisz określić, co masz na myśli, mówiąc "najlepsze" - dla niektórych ważna jest szybkość, która kwalifikuje odpowiedź jako "najlepsza" - dla innych, mogą wybaczyć kilkaset milisekund, jeśli rozwiązanie było bardziej czytelne.

"Najlepszy" jest subiektywny, chyba że jesteś bardziej konkretny.


To mówi:

Iteruj przez liczby, dla każdego numeru przeszukuj listę dla tego numeru, a kiedy osiągniesz liczbę, która zwraca tylko 1 dla liczby wyników wyszukiwania, skończysz.


0
2017-08-29 20:07





Wygląda na to, że najlepsze, co możesz zrobić, to powtórzyć listę, bo każdy element dodaje go do listy "widzianych" przedmiotów lub usuwa go z "widocznego", jeśli już tam jest, a na końcu twoja lista "widzianych" "przedmioty będą zawierały 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, tak naprawdę nie ma znaczenia, ponieważ nie ma nic szczególnego, co można zrobić, dodając je ... czy istnieje?

Pytanie

Nie rozumiem, dlaczego wybrana odpowiedź jest "najlepsza" według dowolnego standardu. O (N * lgN)> O (N), i zmienia listę (lub tworzy jej kopię, która jest wciąż droższa w przestrzeni i czasie). Czy czegoś brakuje?


0
2017-08-29 20:12





Zależy od tego, jak duże / małe / zróżnicowane są liczby. Może być zastosowany sortowanie radix, które w dużym stopniu ograniczyłoby czas sortowania rozwiązania O (N log N).


0
2017-08-29 20:33





Metoda sortowania i metoda XOR mają złożoność w tym samym czasie. Metoda XOR jest tylko O ​​(n), jeśli założysz, że bitowe XOR dwóch ciągów jest operacją o stałym czasie. Jest to równoznaczne z powiedzeniem, że wielkość liczb całkowitych w tablicy jest ograniczona przez stałą. W takim przypadku możesz użyć sortowania Radix do posortowania tablicy w O (n).

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


0
2017-09-01 06:21





Możesz po prostu umieścić elementy w zestawie w hasz tak długo, aż znajdziesz kolizję. W rubinach jest to jeden liniowiec.

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.

Jest to jednak typowe pytanie typu "trick". Zazwyczaj jest to lista kolejnych liczb całkowitych z jednym zduplikowaniem. W tym przypadku ankieter często szuka cię, abyś użył sumy Gaussa n- sztuczki, np. n*(n+1)/2 odjąć od rzeczywistej sumy. Odpowiedź podręcznika jest właśnie taka.

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

-1
2017-08-29 20:27