Jeden element, który różni się dwiema tablicami. Jak znaleźć to skutecznie?

Przygotowuję się do wywiadu na temat programowania i naprawdę nie mogę znaleźć najbardziej skutecznego sposobu rozwiązania tego problemu.

Załóżmy, że mamy dwie tablice składające się z liczb nieposortowanych. Tablica 2 zawiera liczbę, której nie ma tablica 1. Obie tablice mają losowo rozmieszczone liczby, niekoniecznie w tej samej kolejności lub przy tych samych indeksach. Na przykład:

Tablica 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Tablica 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

Jaki jest najszybszy algorytm znajdowania różnej liczby? Jaki jest jego czas działania? W tym przykładzie liczba, której szukamy, to 21.

Mój pomysł polegał na przejściu przez tablicę 1 i usunięciu tej wartości z tablicy 2. Iteruj, aż skończysz. Powinno to być mniej więcej w czasie , prawda?$O(n \log n)$

Widzę cztery główne sposoby rozwiązania tego problemu, z różnymi czasami działania:

• Rozwiązanie O ( n 2 ) : to byłoby rozwiązanie, które zaproponujesz. Należy pamiętać, że ponieważ tablice są nieposortowane, usuwanie trwa liniowo. Dokonujesz n usunięcia; dlatego ten algorytm zajmuje kwadratowy czas.$O(n^2)$$n$

• rozwiązanie: uprzednio posortuj tablice; następnie wykonaj wyszukiwanie liniowe, aby zidentyfikować odrębny element. W tym rozwiązaniu czas wykonywania jest zdominowany przez operację sortowania, stąd O ( $O(n \: log \: n)$ górna granica.$O(n \: log \: n)$

Kiedy znajdziesz rozwiązanie problemu, zawsze powinieneś zadać sobie pytanie: czy mogę to zrobić lepiej? W tym przypadku możesz, sprytnie wykorzystując struktury danych. Zauważ, że wszystko, co musisz zrobić, to powtórzyć jedną tablicę i powtórzyć wyszukiwanie w drugiej tablicy. Jaka struktura danych pozwala na wyszukiwanie w (oczekiwanym) stałym czasie? Zgadłeś dobrze: tablica skrótów .

• rozwiązanie (oczekiwane): iteruj pierwszą tablicę i przechowuj elementy w tablicy mieszającej; następnie wykonaj skanowanie liniowe w drugiej tablicy, sprawdzając każdy element w tablicy skrótów. Zwraca element, którego nie ma w tabeli skrótów. To rozwiązanie czasu liniowego działa dla każdego typu elementu, który można przekazać do funkcji skrótu (np. Działałoby podobnie dla tablic ciągów znaków).$O(n)$

Jeśli chcesz mieć górne granice gwarancji, a tablice są ściśle złożone z liczb całkowitych, najlepszym rozwiązaniem jest prawdopodobnie to, które zaproponował Tobi Alafin (nawet jeśli to rozwiązanie nie da ci indeksu elementu, który różni się w drugiej tablicy) :

• rozwiązanie (gwarantowane): zsumuj elementy pierwszej tablicy. Następnie zsumuj elementy drugiej tablicy. Na koniec wykonaj odejmowanie. Zauważ, że to rozwiązanie może być uogólnione na dowolny typ danych, którego wartości mogą być reprezentowane jako ciągi bitów o stałej długości, dziękibitowemu operatorowi XOR. Jest to dokładnie wyjaśnione w odpowiedziIlmari Karonena. $O(n)$

Wreszcie, inną możliwością (przy takim samym założeniu tablic liczb całkowitych) byłoby użycie algorytmu sortowania w czasie liniowym, takiego jak sortowanie zliczające. Skróciłoby to czas działania rozwiązania opartego na sortowaniu od do O ( n ) .$O(n \: log \: n)$$O(n)$

Rozwiązanie różnicy sum zaproponowane przez Tobiego i Mario można w rzeczywistości uogólnić na dowolny inny typ danych, dla którego możemy zdefiniować operację binarną (o stałym czasie) ⊕, która:$\Theta(n)$$\oplus$

• Całkowita tak, że dla wszystkich wartości i b , ⊕ b jest określony i tego samego rodzaju (przynajmniej w pewnym odpowiednim supertypem nim, na którym operator ⊕ wciąż wyżej);$a$$b$$a \oplus b$$\oplus$
• asocjacyjny , taki, że ;$a \oplus (b \oplus c) = (a \oplus b) \oplus c$
• przemienne , takie, że ; i$a \oplus b = b \oplus a$
• anulujący , taki, że istnieje operator odwrotny który spełnia ( a ⊕ b ) ⊖ b = a . Technicznie rzecz biorąc, ta odwrotna operacja niekoniecznie musi być czasem stałym, o ile „odjęcie” dwóch sum n elementów nie zajmuje więcej niż O ( n ) czasu.$\ominus$$(a \oplus b) \ominus b = a$$n$${\rm O}(n)$

(Jeśli typ może przyjąć tylko skończoną liczbę odrębnych wartości, właściwości te są wystarczające, aby przekształcić go w grupę abelową ; nawet jeśli nie, będzie to przynajmniej przemienna półgrupa anulacyjna ).

Za pomocą takiej operacji możemy zdefiniować „sumę” tablicy a = ( a 1 , a 2 , … , a n ) jako ( $\oplus$$a = (a_1, a_2, \dots, a_n)$ Biorąc pod uwagę macierz drugiego b = ( b 1 , b 2 , ... , b n , b, n + 1 ) , zawierający wszystkie elementyplus jeden dodatkowy element X , mamy więc (

Na przykład, jeśli wartości w tablicach są liczbami całkowitymi, to dodawanie liczb całkowitych (lub dodawanie modułowe dla typów liczb całkowitych o skończonej długości) może być użyte jako operator , z odejmowaniem jako operacja odwrotna ⊖ . Alternatywnie, dla dowolnego typu danych, którego wartości mogą być reprezentowane jako ciągi bitów o stałej długości, możemy użyć bitowego XOR jako ⊕ i ⊖ .$\oplus$$\ominus$$\oplus$$\ominus$

Mówiąc bardziej ogólnie, możemy nawet zastosować bitową metodę XOR do łańcuchów o zmiennej długości, wypełniając je do tej samej długości, jeśli to konieczne, o ile mamy jakiś sposób na odwrócenie usunięcia wypełnienia na końcu.

W niektórych przypadkach jest to banalne. Na przykład ciągi bajtowe zakończone znakiem null w stylu C domyślnie kodują własną długość, więc zastosowanie dla nich tej metody jest trywialne: gdy XORing dwóch ciągów, wypełnij krótszy bajtami zerowymi, aby dopasować ich długość, i odetnij dodatkowe końcowe null z Wynik końcowy. Zauważ, że pośrednie łańcuchy sumy XOR mogą zawierać bajty zerowe, więc musisz jawnie zapisać ich długość (ale potrzebujesz tylko jednego lub dwóch z nich).

Mówiąc bardziej ogólnie, jedną metodą, która działałaby dla dowolnych ciągów bitów, byłoby zastosowanie wypełnienia jednobitowego , w którym każdy wejściowy ciąg bitów jest wypełniany jednym bitem, a następnie tyloma bitami 0, ile potrzeba, aby dopasować (wypełnioną) długość najdłuższy ciąg wejściowy. (Oczywiście tego wypełniania nie trzeba wykonywać z wyprzedzeniem; możemy go po prostu zastosować w razie potrzeby podczas obliczania sumy XOR.) Na koniec musimy po prostu usunąć końcowe bity 0 i ostatni 1 bit z wynik. Alternatywnie, gdybyśmy wiedzieli, że struny mają np. Maksymalnie 2 $1$$0$$0$$1$$2^{32}$bajtów długości, możemy zakodować długość każdego łańcucha jako 32-bitową liczbę całkowitą i dodać go do łańcucha. Lub moglibyśmy nawet zakodować dowolne długości ciągów za pomocą jakiegoś kodu prefiksu i wstawić je do ciągów. Istnieją również inne możliwe kodowania.

W rzeczywistości, ponieważ każdy typ danych do zakodowania w komputerze, z definicji, jest przedstawiony jako ciąg bitów skończonej długości, metoda ta daje rodzajowy rozwiązanie tego problemu.$\Theta(n)$

Jedyną potencjalnie trudną częścią jest to, że aby anulowanie zadziałało, musimy wybrać unikalną kanoniczną reprezentację ciągu bitowego dla każdej wartości, co może być trudne (a nawet potencjalnie nierozstrzygalne obliczeniowo), jeśli można podać wartości wejściowe w dwóch tablicach w różnych reprezentacjach równoważnych. Nie jest to jednak szczególna słabość tej metody; każda inna metoda rozwiązania tego problemu może również zawieść, jeśli dane wejściowe mogą zawierać wartości, których równoważność jest nierozstrzygalna.

Zamieściłbym to jako komentarz do odpowiedzi Tobiego, ale nie mam jeszcze reputacji.

Jako alternatywę do obliczania sumy każdej listy (szczególnie jeśli są to duże listy lub zawierają bardzo duże liczby, które mogą przepełnić twój typ danych po zsumowaniu), możesz zamiast tego użyć xor.

Wystarczy obliczyć sumę xor (tj. X [0] ^ x [1] ^ x [2] ... x [n]) dla każdej listy, a następnie x lub te dwie wartości. To da ci wartość obcego elementu (ale nie indeks).

Jest to nadal O (n) i pozwala uniknąć problemów z przepełnieniem.

Element = Sum (Array2) - Sum (Array1)

I szczerze wątpię, że jest to najbardziej optymalny algorytm. Ale to kolejny sposób na rozwiązanie problemu i najprostszy sposób na jego rozwiązanie. Mam nadzieję, że to pomoże.

Jeśli liczba dodanych elementów jest większa niż jeden, to nie zadziała.

Moja odpowiedź ma tę samą złożoność w przypadku najlepszego, najgorszego i przeciętnego przypadku,

EDYCJA
Po namyśle myślę, że moja odpowiedź jest twoim rozwiązaniem.

$n$$n-1$$1 = n-1$$2 = n+1 -1=n$

$2n-1$$2 -$$1 = 1$

$2n - 1 + 1 = 2n$

EDYCJA:
Z powodu pewnych problemów z typami danych, suma XOR, jak sugeruje reffu, będzie bardziej trafna.

Zakładając, że tablica 2 została utworzona przez pobranie tablicy 1 i wstawienie elementu w losowej pozycji, lub tablica 1 została utworzona przez pobranie tablicy 2 i usunięcie losowego elementu.

Jeśli wszystkie elementy tablicy mają być odrębne, czas wynosi O (ln n). Porównujesz elementy w lokalizacji n / 2. Jeśli są równe, dodatkowy element jest od n / 2 + 1 do końca tablicy, w przeciwnym razie wynosi od 0 do n / 2. I tak dalej.

Jeśli nie ma gwarancji, że elementy tablicy będą odrębne: możesz n razy wstawić liczbę 1 w tablicy 1, a liczbę 2 wstawić w dowolnym miejscu w tablicy 2. W takim przypadku nie możesz wiedzieć, gdzie jest liczba 2, nie patrząc wcale elementy tablicy. Dlatego O (n).

PS. Ponieważ wymagania uległy zmianie, sprawdź bibliotekę pod kątem dostępności. Na MacOS / iOS utworzyć NSCountedSet, dodać wszystkie numery z tablicy 2, usunąć wszystkie numery z tablicy 1, a to, co pozostaje, to wszystko, co jest w tablicy 2, ale nie w tablicy 1, nie opierając się na twierdzeniu, że istnieje jeden dodatkowy pozycja.

var najkrótszy, najdłuższy;

Konwertuj najkrótszy na mapę w celu szybkiego odniesienia i zapętlaj najdłuższy, dopóki bieżącej wartości nie będzie na mapie.

Coś takiego w javascript:

if (arr1.length> arr2.length) {shortest = arr2; najdłuższy = arr1; } else {shortest = arr1; najdłuższy = arr2; }

var map = shortest.reduce (function (obj, wartość) {obj [wartość] = true; return obj;}, {});

var różnica = najdłuższy.find (funkcja (wartość) {return !!! map [wartość];});

Rozwiązanie O (N) w złożoności czasowej O (1) pod względem złożoności przestrzeni

Opis problemu: Zakładając, że tablica2 zawiera wszystkie elementy tablicy1 plus jeden inny element nieobecny w tablicy1.

Rozwiązanie jest następujące: Używamy xor, aby znaleźć element, który nie jest obecny w tablicy 1, więc kroki są następujące: 1. Zacznij od tablicy 1 i wykonaj xor wszystkich elementów i zapisz je w zmiennej. 2. Weź tablicę2 i wykonaj xor wszystkich elementów za pomocą zmiennej przechowującej xor tablicy1. 3. Po wykonaniu operacji nasza zmienna będzie zawierać element, który jest obecny tylko w tablicy2. Powyższy algorytm działa z powodu następującej właściwości xor "a xor a = 0" "a xor 0 = a" Mam nadzieję, że to rozwiąże twój problem. Również wyżej sugerowane rozwiązania są również w porządku