Pytanie Algorytm znajdowania powtarzającej się liczby na liście, która może zawierać dowolną liczbę powtórzeń


Przeczytaj uważnie to pytanie, zanim zamkniesz je jako duplikat, ale jeśli jest to szczery duplikat, chętnie się o tym dowiem. To jest uogólnienie Znajdź jedną z wielu możliwych powtórzonych liczb całkowitych na liście.

Biorąc pod uwagę dowolny zestaw S z N odrębny   liczby całkowite i dowolna tablica ZA z   długość N + 1 każdy wpis jest   pochodzi z S, co jest najlepsze   algorytm do znalezienia niektórych (musi być   co najmniej jeden) wielokrotny wpis ZA?

UWAGA: Może być wiele powtórzonych wpisów w ZA, a każdy wpis można powtórzyć wiele razy.

Jak wskazuje Nemo, rozwiązanie jest trywialne O (1) przestrzeń i O (N ^ 2) czas. Szukam rozwiązania, które poprawia czas bez nadmiernego ograniczania przestrzeni. Aby być precyzyjnym, szukam rozwiązań, których szukam:

  • Zwraca wartość za pojawia się w ZA co najmniej dwukrotnie,
  • Wykorzystuje co najwyżej O (log N) przestrzeń bez modyfikowanie ZA, i
  • Zajmuje mniej niż O (N ^ 2) czas

EDYTOWAĆ: Zbiór S jest tam, aby zapewnić, że macierz ZA ma co najmniej jeden powtórny wpis. W tym przypadku nie zakładaj, że masz S dany ci jako uporządkowany zestaw. Możesz zapytać S (Boolean, aby powrócić true jest s w S i false w przeciwnym razie) i możesz zapytać ZA (zadzwonić po A [i]), ale to wszystko. Każde rozwiązanie, które sortuje ZA lub S przekracza limit miejsca.

To uogólnienie unieważnia moje rozwiązanie wskaźnika do pierwotnego pytania (które ma O (1) przestrzeń i NA) czas), a ograniczenie przestrzeni, które narzucam, unieważnia rozwiązanie Fiver (który ma NA) przestrzeń i czas).


12
2018-06-22 00:04


pochodzenie


Traverse Zakładanie przedmiotów w tabeli mieszającej. Jeśli przedmiot istnieje w tabeli mieszania, wiesz, że jest duplikatem. Traversing A to O (N), szukanie w ha ha to O (logN). Tak więc złożoność czasu jest nlogn. Przestrzeń to N dla hashtable. Moim założeniem jest, że tablica haszująca jest wspierana przez zrównoważone drzewo, które wymaga logN do wyszukania elementu. Klucz hash to element, a wartość to liczba wystąpień. - Ryan Reeves
@Ryan: To brzmi bardziej jak odpowiedź niż komentarz. Tabela mieszająca zajmuje przestrzeń O (N), prawda? Chcę mieć więcej niż O (log N) dla przestrzeni. - PengOne
Przykro mi, źle odczytałem twój wpis. Czytam przestrzeń O (n ^ 2). - Ryan Reeves
Czekaj, czy powiedziałeś czas O (N ^ 2) i O (log N)? Ponieważ jestem prawie pewny, że przeciętny piątoklasista mógł to zrobić w czasie O (N ^ 2) i stałej przestrzeni ... :-) - Nemo
Jesteśmy powiedział S, czy wiemy po prostu, że elementy w A pochodzą z jakiegoś zbioru S? Równoważnie, czy wiemy po prostu, że w A jest co najwyżej N różnych elementów, czy też wiemy, czym one są? Jeśli wiemy, czym one są, w jaki sposób dostarczana jest ta wiedza? (Np. Jeśli S jest przedstawiane jako posortowana lista, wówczas "indeks numeryczny" 0 <= i <N pozycji można znaleźć w czasie log N). - j_random_hacker


Odpowiedzi:


Algorytm ten jest podobny do algorytmu Justina Simona, ale kluczową kwestią jest obliczenie mediany (lub k-tego elementu) S przy użyciu efektywnie przestrzeni O (1).

Oto kluczowy algorytm, który jest losowy:

Ustaw niższy równy minimalnemu elementowi S, a górna równy maksymalnemu elementowi S. Wybierz losowy element x z S, który jest pomiędzy dolnym a górnym (to kosztuje co najwyżej O (n) spodziewanego czasu). Oblicz rangę x (czas O (n)). Jeśli ranga x jest zbyt niska, ustaw niższą wartość na następcę x (czas O (n)), w przeciwnym razie ustaw górną wartość równą poprzednikowi czasu x (O (n)). Powtarzaj aż do uzyskania niższej wartości górnej.

Zauważ, że każda iteracja kosztuje O (n) w oczekiwaniu i są iteracje O (lg n) w oczekiwaniu, więc oczekiwany koszt czasu wynosi O (n lg n), a wykorzystanie przestrzeni jest O (1), ponieważ przechowujemy tylko niższe i wyższe wartości.

Używając tej umiejętności, aby wybrać element kt, możemy użyć zasada szufladki zgodnie z sugestią oryginalne pytanie aby znaleźć coraz mniejsze segmenty S, które zawierają zbyt wiele elementów, aby każdy mógł je odróżnić, używając O (lg n) liniowych skanów przestrzeni A i O (1) do przechowywania odpowiednich sum elementów w każdym regionie. Każda taka iteracja kosztuje O (n) oprócz kosztu O (n lg n) znalezienia elementu kt, a są iteracje O (lg n), więc całkowity koszt wynosi O (n lg ^ 2 n).


7
2018-06-22 17:37



Nie rozumiem niektórych z tego. Co masz na myśli przez "rangę x" i "następcę x"? Czyta się tak, jak posortowałeś S, która zajmuje przestrzeń O (N). - PengOne
Następcą x jest minimalny element (lub "a" element minimalny) większy niż x. Można to znaleźć, wykonując iterację po S, przechowując tylko najmniejszy element większy niż x spośród S [1..i]. - jonderry
BTW, mam wrażenie, że musi istnieć problem z tym algorytmem, ponieważ nie mogę znaleźć odniesienia do niego w Internecie. Istnieją bardziej skomplikowane algorytmy do znalezienia mediany, ale nie do końca osiągają te same granice. Nadal będą zadowoleni z granic, których szukasz. Widzieć ten papier. - jonderry
@jonderry: Podejrzewam, że znajdujesz medianę, ale bardzo podoba mi się ten pomysł. Pomyślę o tym wieczorem i zobaczę, co wymyślę. Jak dotąd ta odpowiedź jest najbardziej obiecująca. Dziękuję za przemyślenie tego pytania! - PengOne
@PengOne, myślę, że w mojej odpowiedzi znalazłem odniesienie do mediany algorytmu ten dziennik. Nie mam dostępu do artykułu, ale widzę odpowiedni tekst w fragmencie wyniku wyszukiwania Google (spróbuj Googling "najmniejszego elementu z tablicy tylko do odczytu"). - jonderry


Znajdź punkt środkowy zbioru S liczb całkowitych N (jeśli są one kolejne, to jest to trywialne, w przeciwnym razie można to zrobić w O (logn)).

Przejrzyj listę A, obliczyć liczbę wpisów, które są mniejsze niż ten punkt środkowy. Więc masz więcej wpisów w A mniej niż twój punkt środkowy niż różne liczby w S, które robią to samo, lub masz mniej wpisów w A mniej niż twój środek, itd. W pierwszym przypadku weź wpisy poniżej punktu środkowego i powtarzajcie, w tym drugim bierzcie to, co jest większe lub równe temu.

To rozwiązanie działa w n (log (n)) ^ 2 razy, jak sądzę.


0
2018-06-22 00:59



@ Justin: Jest to zasadniczo rozwiązanie zaproponowane przez Daniela dla jego oryginalne pytanie. Przechowywanie wartości w celu znalezienia punktu środkowego NA) przestrzeń. - PengOne
Jak znaleźć medianę w czasie logarytmicznym? Wiem tylko Na) algorytmy wyboru, a nawet modyfikować S podczas biegu. - IVlad
Masz 100% racji! Błędnie pamiętam coś z algorytmów. Jednak jeśli S został posortowany, możesz to zrobić w stałym czasie - Justin Simon
Ten algorytm działa i działa w czasie O (n lg ^ 2 n) i O (1). Łatwo jest wybrać i ten element S w czasie O (n lg n) i O (1). - jonderry
@j_random_hacker: Nie rozumiem twojego sprzeciwu. Jeśli wiem, że przedział [A, B] zawiera p odrębne wartości w S i> = p + 1 w A, a C to punkt środkowy [A, B], to albo [A, C] albo [C, B) zawiera q odrębnych wartości w S i> = q + 1 wartości w A. W twoim przykładzie, powiedzmy S = {2,3,42}, warunek wejścia jest taki, że [2, \ infty] ma 3 wartości w Wartości S i 4 w A, i biorąc C = 3 otrzymuję [2,3], który ma 1 wartość S i 2 w A. Zachowuje to, jeśli "punkt środkowy" jest dowolnie (A, B). - xofon


Autor książki Znajdowanie zduplikowanych elementów w tablicy sugeruje, że nawet gdyby jeden przydzielić tablicę bitów do reprezentowania każdej możliwej liczby całkowitej (całkiem zarządzalna 2 bitowa 24 bitowa tablica daje jeden bit na każdą 32-bitową liczbę całkowitą) nadal byłaby zdefiniowana jako wykorzystująca przestrzeń O (1) i zwykle się zgadzam.

Dlatego najprostszy możliwy algorytm, który testuje i ustawia bit reprezentujący każdą liczbę całkowitą znalezioną w tablicy, zwracając duplikat liczby całkowitej, jeśli bit jest już ustawiony, działałby w czasie O (n) i używał przestrzeni O (1).


0
2017-11-11 04:42





Jeśli możemy zmienić tablicę, myślę, że możemy to zrobić za pomocą sortowania segmentów w miejscu w czasie O (n) i O (1) dodatkowej przestrzeni.

W szczególności przejrzyj każdy element na liście. Dla każdego elementu sprawdź, czy ta liczba jest równa indeksowi. Jeśli nie, zastąp tę liczbę elementem w indeksie, aż indeks i liczba będą takie same. Jeśli zobaczysz ten sam numer w nowym indeksie, to duplikat.


-1
2017-11-05 01:12



To nie daje odpowiedzi na pytanie. Kiedy już wystarczy reputacja będziesz w stanie skomentuj dowolny wpis; zamiast, udzielać odpowiedzi, które nie wymagają wyjaśnień od pytającego. - Z recenzji - Stefan Svrkota