Biorąc nieposortowaną sekwencję [1, ..., n] liczb całkowitych, podaj algorytm wykonawczy O (nlogn), aby sprawdzić, czy istnieją dwa indeksy i i j takie, że a [i] = 2 * a [j] . Algorytm powinien zwrócić i = 0 i j = 2 na wejściu 4,12,8,10 i wartość false na wejściu 4,3,1,11.Sprawdź, czy istnieje [i] = 2 * a [j] w nieposortowanej tablicy a?
Myślę, że musimy sortować tablicę i tak, to jest O (nlogn). Nie jestem pewien, co robić później.
Masz rację, że pierwszym krokiem jest posortowanie tablicy.
Po posortowaniu tablicy można sprawdzić, czy dany element znajduje się wewnątrz tablicy w czasie O(log n). Więc jeśli dla każdego elementu n sprawdzasz, czy włączono inny element w czasie O(log n), kończy się to runtime z O(n log n).
Czy to ci pomoże?
Krok 1 to O (n), a krok 2 i 3 to O (n * log n).
Możesz także wykonać krok 3 w O (n) (nie ma potrzeby wyszukiwania binarnego). Ponieważ jeśli odpowiadający element A [i] jest w A [j], wówczas odpowiedni element dla A [i + 1] nie może być w A [0..j-1]. Możemy więc zachować dwa wskaźniki i znaleźć odpowiedź w O (n). Ale w każdym razie, cały algorytm będzie O (n log n), ponieważ wciąż sortujemy.
Krok 1 wydaje się superflou ... Nie używasz do niczego drugiej wartości par. – Alderath
Myślę, że algorytm powinien zwrócić indeksy i i j. To jest powód dla drugiego elementu. –
Sortowanie macierzy jest dobrą opcją - O (nlogn), zakładając, że nie masz jakiejś fantazyjnej opcji sortowania wiadra.
Po to sortowane, trzeba przejść tylko przez tablicę dwukrotnie - Wierzę, że to jest O (n)
Utwórz listę „Doubles”, który rozpoczyna się pusta.
Następnie dla każdego elementu tablicy:
dodać jej podwójnie na końcu listy do" Dwójki
idź dalej, aż znajdziesz podwójne lub dojdziesz do końca swojej pierwszej listy.
O(n log n) lub O(n) jeśli jesteś gotów do rozciągnięcia punkt o macierzach liczb całkowitych o stałej wielkości)O(1))fastPonieważ każdy z fast i slow może być zwiększana co najwyżej n razy łączne przed osiągnięciem końca tablicy , "wielokrotnie" część to O(n).
to jest najlepsza odpowiedź, powinny zostać zaakceptowane. –
Uwaga: , które mogą być wykonane na O(n) średnio, stosując hash table.
set <- new hash set
for each x in array:
set.add(2*x)
for each x in array:
if set.contains(x):
return true
return false
Dowód:
=>
Jeśli istnieją 2 elementy a[i] i a[j] takie, że a[i] = 2 * a[j], następnie podczas iteracji po raz pierwszy, możemy dodaje 2*a[j] do zestawu, gdy czytamy a[j]. W drugiej iteracji stwierdzamy, że a[i] == 2* a[j] jest w zestawie i zwraca true.
< =
Jeżeli algorytm powrócił prawda, to okaże się, że taki a[i]a[i] jest już w komplecie w drugiej iteracji. Tak więc, podczas pierwszej itetacji - wstawiliśmy a[i]. To można zrobić tylko wtedy, gdy jest drugi element a[j] taki, że a[i] == 2 * a[j], i wstawiliśmy a[i] podczas czytania a[j].
Uwaga:
W celu powrotu indeksom elemets, można po prostu użyć hash-mapy zamiast zestawu, a dla każdego i sklepie 2*a[i] jako klucz i i jako wartości.
przykład: Input = [4,12,8,10]
pierwsza wkładka dla każdego x - 2X do tabeli mieszania i indeksu.Dostaniesz:
hashTable = {(8,0),(24,1),(16,2),(20,3)}
Teraz na secod iteracji sprawdzić dla każdego elementu, jeśli jest w tabeli:
arr[0]: 4 is not in the table
arr[1]: 12 is not in the table
arr[2]: 8 is in the table - return the current index [2] and the value of 8 in the map, which is 0.
tak, wyjście końcowa wynosi 2,0 - zgodnie z oczekiwaniami.
(1) Złożoność Wskazówka:
Tutaj, O(n) zakłada O(1) funkcji skrótu. Nie zawsze tak jest. Jeśli przyjmiemy funkcję mieszania O(1), możemy również założyć, że sortowanie za pomocą radix-sort to O(n) i przy użyciu przetwarzania końcowego z O(n) [podobnego do sugerowanego przez @SteveJessop w jego odpowiedzi], możemy również uzyskać O(n) z sortowaniem- oparty algorytm.
I w tym przypadku, jeśli tablica hasza to 'O (n)', wówczas sortowanie jest również 'O (n)' przy użyciu sortowania radialnego. –
@SteveJessop: Zakładam, że istnieje pewien punkt w tym, co mówisz, to sprawia, że rozwiązanie oparte na hashu 'O (nlogk)' gdzie 'k' jest możliwym zakresem elementów i przy założeniu' k> = n' [w przeciwnym razie odpowiedź jest trywialne z zasady pieonihole], tutaj nie ma poprawy. ** Usuwam tę odpowiedź za kilka minut ** [dając ci czas na przeczytanie tego komentarza, zanim to zrobię]. – amit
Myślę, że twoja odpowiedź jest całkowicie rozsądna: rozwiązuje problem z dobrą wydajnością za pomocą narzędzi po wyjęciu z pudełka. Chodzi tylko o podzielenie włosów na złożoność operacji na liczbach całkowitych o stałej wielkości, co oznacza, że zarówno zestaw skrótu, jak i sortowanie w formacie binarnym w pewnym sensie "oszukuje", aby odebrać 'O (n)'. Albo nie oszukujesz, w takim przypadku masz rację, że 'O (n log n)' nie jest ścisłym ograniczeniem. –
Można również użyć zbalansowanego drzewa, ale wykorzystuje ono dodatkową przestrzeń, ale także nie szkodzi macierzy.
Począwszy od i=0, i zwiększając i, wstaw elementy, sprawdzając, czy dwa razy lub połowa obecnego elementu jest już w drzewie.
Jedną z korzyści jest to, że będzie działać w O(M log M) czasie, gdzie M = min [max{i,j}]. Można potencjalnie zmienić algorytm sortowania na próbę, aby spróbować i zrobić O(M log M), ale może się skomplikować.
Btw, jeśli tylko przy użyciu porównań istnieje Omega(n log n) dolny, poprzez zmniejszenie problemu elementem odrębności tego:
Duplikat tablicy wejściowej. Użyj algorytmu dla tego problemu dwa razy. Więc jeśli nie wprowadzisz do obrazu elementów mieszających, nie możesz uzyskać lepszego niż algorytm Theta(n log n)!
Wybieram to jako właściwą odpowiedź, ponieważ chociaż odpowiedź @amit była elegancka, zakłada się, że mamy dwa razy większą przestrzeń i funkcję skrótu O (1). Gdybym mógł wybrać dwie odpowiedzi, wybrałbym też odpowiedź Steve'a. –
Hej, nadal musisz śledzić oryginalne wskaźniki, więc nadal potrzebujesz dodatkowej przestrzeni :) –
@VictorParmar Przypis nie mówi, że musisz zwrócić indeksy. "Sprawdź, czy ..." brzmi dla mnie, jakby pytał o funkcję boolowską (więc nie trzeba pamiętać indeksów). – sepp2k