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

22

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)$

— Konstantino Sparakis
źródło

@Jandvorak Dziękuję wam za odpowiedzi. Nie spałem późno i zdarzyło mi się zasnąć po opublikowaniu tego. Tablica jest nieposortowana, a wszystkie elementy pojawiają się w losowych indeksach w obu tablicach.

— Konstantino Sparakis,

@KonstantinoSparakis: to wyjaśnienie unieważnia odpowiedzi, które zakładają, że obie tablice zawierają elementy w tych samych pozycjach.

— Mario Cervera,

Cross posting jest skrzywdzony na softwareengineering.stackexchange.com/users/256931/...

— paparazzo

@Paparazzi Po prostu szukałem rozwiązania, które przeczytałem w meta inżynierii oprogramowania, gdzie szukać rozwiązania, ale wtedy nie wiedziałem o forum CS. Powiadomiłem modów, żeby to wyczyściły.

— Konstantino Sparakis,

@Paparazzi czy istnieje meta post, który tworzy kopię zapasową? Osobiście nie widzę żadnego sposobu na dobre wdrożenie tej polityki.

— djechlin

30

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

Rozwiązanie : to byłoby rozwiązanie, które zaproponujesz. Należy pamiętać, że ponieważ tablice są nieposortowane, usuwanie trwa liniowo. Dokonujesz 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(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 \: log \: n)$ $O(n)$

— Mario Cervera
źródło

4

sumowanie nie jest jednak liniowe, jeśli liczby stają się wystarczająco duże.

— Sarge Barszcz

9

Jedną fajną rzeczą w algorytmie sumowania jest to, że działa on z dowolną grupą abelową, nie tylko z liczbami całkowitymi (przede wszystkim uint64; cc @sarge).

— John Dvorak,

6

@ Abdul chodzi o to, że jeśli twoje liczby całkowite są bardzo duże, nie możesz już udawać, że dodają

. Uważam, że złożoność rośnie do

jeśli się na to zgodzi. Jednak użycie XOR zamiast zwykłego dodawania rozwiązuje ten problem, jednocześnie pozwalając na dowolnie dużą liczbę danych wejściowych.

O (n)

$O(n)$

O (n \ln n)

$O(n \ln n)$

— John Dvorak,

2

@JanDvorak Nie, nie ma. Zakładasz, że operacja zdefiniowana na grupie abelowej zajmuje cały czas. Tego nie można po prostu założyć.

— UTF-8

2

@ UTF-8 Nie zakładam tego. Jednak czyni to w grupach skończonych (uint64), w miejscu cyfr mądry dodatek (dodatkiem w

) jest liniowa wielkości out-of miejscu argumentu. Zatem obliczenie sumy w takich grupach jest czasem liniowym w całkowitej wielkości operandów.

{Z_{n}}^{d}

${Z_n}^d$

— John Dvorak,

16

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 , 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 . Technicznie rzecz biorąc, ta odwrotna operacja niekoniecznie musi być czasem stałym, o ile „odjęcie” dwóch sum elementów nie zajmuje więcej niż 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 jako $\oplus$ $a = (a_1, a_2, \dots, a_n)$ Biorąc pod uwagę macierz drugiego , zawierający wszystkie elementyplus jeden dodatkowy element , mamy więc

(\oplus a) = a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} .

$(\oplus\, a) = a_1 \oplus a_2 \oplus \dotsb \oplus a_n.$

b = (b_{1}, b_{2}, \dots, b_{n}, b_{n + 1})

$b = (b_1, b_2, \dots, b_n, b_{n+1})$

a

$a$

x

$x$

, więc możemy znaleźć ten dodatkowy element, obliczając:

(\oplus b) = (\oplus a) \oplus x

$(\oplus\, b) = (\oplus\, a) \oplus x$

x = (\oplus b) ⊖ (\oplus a) .

$x = (\oplus\, b) \ominus (\oplus\, a).$

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 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 i ostatni bit z wynik. Alternatywnie, gdybyśmy wiedzieli, że struny mają np. Maksymalnie $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.

— Ilmari Karonen
źródło

Wow, bardzo ciekawe podejście do tego. Dziękuję @IlmariKaronen

— Konstantino Sparakis,

14

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.

— reffu
źródło

3

Użyłbym również XOR, ponieważ wydaje się to nieco bardziej uporządkowane, ale szczerze mówiąc, przepełnienie nie jest tak naprawdę problemem, o ile język, w którym implementujesz to obsługuje przepełnienie przez zawijanie.

— Martin Ender

14

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$

Θ (n)

$\Theta(n)$

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

— Tobi Alafin
źródło

Należy pamiętać, że ta metoda może nie dać dokładnej odpowiedzi, jeśli wartości są zmienne, ponieważ sumowanie liczb może powodować błędy zaokrąglania. Będzie jednak działał dla wartości liczb całkowitych, pod warunkiem, że albo: a) typ liczby całkowitej ma dobrze zdefiniowane zachowanie zawijania w przypadku przepełnienia, lub b) przechowujesz sumy w zmiennych typu wystarczająco szerokiego, aby nie mogły się przepełnić.

— Ilmari Karonen,

Klasa Ruby „BigNum” prawdopodobnie sobie z tym poradzi.

— Tobi Alafin,

Absolutnie nie działa, jeśli tablica zawiera na przykład ciągi lub prawie wszystko, czego nie można znacząco dodać.

— gnasher729,

Tak, zrozumiałem. Co z użyciem „XOR”? Czy to będzie działać dla pływaków?

— Tobi Alafin

Tak, a także wskaźniki i ogólnie wszystko, co składa się ze stałej liczby bitów. Wiele języków tego nie obsługuje, ale nie jest to podstawowy problem. Modułowe dodawanie / odejmowanie będzie działać w tych samych przypadkach.

— Harold

1

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.

— gnasher729
źródło

Ta odpowiedź była natychmiastowa, ale pytanie zostało edytowane z nowym wymaganiem, które unieważnia twoje założenie.

— Mario Cervera,

Twoja nowa odpowiedź wydaje się słuszna. Jaka jest złożoność czasu.

— Tobi Alafin

Po pierwsze, jaki jest czas potrzebny na napisanie kodu. To banalne. NSCountedSet używa mieszania, więc złożoność czasu jest „zwykle liniowa”.

— gnasher729,

-1

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ść];});

— Craig Hardcastle
źródło

Kody bez wyjaśnień nie są tutaj dobrą odpowiedzią. Również dlaczego miałbyś skorzystać !!! ?

— Zły

-1

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

— Głupi błąd
źródło