Mediana of Lists

Question

Poproszono mnie to pytanie:

Otrzymujesz dwie listy liczb całkowitych, z których każdy jest posortowana w kolejności rosnącej i każdy z nich ma długość n. Wszystkie liczby całkowite z obu list są różne. Chcesz znaleźć n-ty najmniejszy element unii dwóch list. (Oznacza to, że po połączeniu list i posortowaniu uzyskanej listy w porządku rosnącym element, który byłby na n-tej pozycji.)

Moje rozwiązanie: Załóżmy, że lista jest zindeksowana.

O (n) roztworu: zastosowania prostego rozwiązania jest zauważyć, że kolumny są wstępnie posortowane tak, że można je połączyć i zatrzymać po n krokach. Pierwsze elementy n-1 nie muszą być kopiowane do nowej tablicy, więc to rozwiązanie zabiera O (n) czas i pamięć O (1).

O (log2 n) roztworu: Roztwór O (log2 n) wykorzystuje ZASTĘPCÓW przeszukiwanie binarne w każdej listy. W skrócie, bierze środkowy element w bieżącym interwale wyszukiwania na pierwszej liście (l1 [p1]) i wyszukuje go w l2. Ponieważ elementy są unikalne, znajdziemy co najwyżej 2 wartości najbliższe l1 [p1]. W zależności od ich wartości w stosunku do l1 [p1-1] i l1 [p1 + 1] oraz ich indeksów p21 i p22, zwracamy n-ty element lub rekurencyjny: Jeśli suma dowolnych z (najwyżej) 3 indeksy w l1 można łączyć z jednym z (najwyżej) 2 indeksów w l2, tak aby l1 [p1 '] i l2 [p2'] znajdowały się obok siebie w posortowanym zjednoczeniu dwóch list i p1 '+ p2 '= n lub p1' + p2 '= n + 1, zwracamy jeden z 5 elementów. Jeśli p1 + p2> n, powracamy do lewej połowy przedziału szukania w l1, w przeciwnym razie powracamy do właściwego przedziału. W ten sposób, dla O (log n) możliwych punktów środkowych w l1, wykonujemy wyszukiwanie binarne O (log n) w l2. Dlatego czas działania wynosi O (log2 n).

O (log n) rozwiązanie: Zakładając, że l1 wykazy i L2 mają stały czas dostępu do któregokolwiek z ich elementów, my mogą korzystać zmodyfikowaną wersję wyszukiwania binarnego, aby uzyskać O rozwiązanie (n log). Najłatwiejszym sposobem jest wyszukiwanie indeksu p1 na jednej z list i obliczanie odpowiedniego indeksu p2 na drugiej liście, tak aby p1 + p2 = n przez cały czas. (Założono, że listy są indeksowane od 1.) Najpierw sprawdzamy, czy nie ma wyjątku, gdy wszystkie elementy z jednej listy są mniejsze niż jakikolwiek element z drugiej listy: Jeśli l1 [n] < l2 [0] zwróci l1 [n ]. Jeśli l2 [n] < l1 [0] zwróci l2 [n]. Jeżeli nie można znaleźć najmniejszy element, n-ty dzień po tym etapie, połączenia findNth (1 N) w przybliżeniu w pseudokodzie:

findNth(start,end) 
p1 = (start + end)/2 
p2 = n-p1 
if l1[p1] < l2[p2]: 
    if l1[p1 + 1] > l2[p2]: 
     return l2[p2] 
    else: 
     return findNth(p1+1, end) 
else: 
    if l2[p2 + 1] > l1[p1]: 
     return l1[p1] 
else: 
    return findNth(start,p1-1) 

element L2 [P2] jest zwrócona przy L2 [P2] jest większy niż dokładnie p1 + p2-1 = n-1 elementy (i dlatego jest n-ta najmniejsza). l1 [p1] jest zwracana w tych samych lecz symetrycznych warunkach. Jeśli l1 [p1] < l2 [p2] i l1 [p1 + 1] < l2 [p2], pozycja l2 [p2] jest większa niż n, więc musimy wziąć więcej elementów z l1 i mniej z l2. Dlatego szukamy p1 w górnej połowie poprzedniego interwału wyszukiwania. Z drugiej strony, jeśli l2 [p2] < l1 [p1] i l2 [p2 + 1] < l1 [p1], pozycja l1 [p1] jest większa niż n. Dlatego prawdziwe p1 będzie leżeć w dolnej połowie naszego bieżącego interwału wyszukiwania. Ponieważ zmniejszamy o połowę rozmiar problemu przy każdym wywołaniu findNth i musimy zrobić tylko stałą pracę, aby zmniejszyć o połowę problem, rekurencyjność tego algorytmu jest T (n) = T (n/2) + O (1), który ma rozwiązanie czasu O (log n).

Ankieter ciągle pyta mnie o różne podejścia do powyższego problemu. Zaproponowałem powyżej trzy podejścia.Czy są one poprawne? Czy istnieje inne najlepsze możliwe rozwiązanie tego pytania? Właściwie to pytanie zadawane wiele razy, więc proszę podać kilka dobrych rzeczy na ten temat.

Answer 1

Nie wiem, czy pan przyjrzał się temu http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

To rozwiązanie bardziej uogólnioną wersję problemu Pytasz o. Zdecydowanie logiczna złożoność jest możliwa ...

Answer 2

Myślę, że to będzie najlepsze rozwiązanie. .

->1 2 3 4 5 6 7 8 9 
->10 11 12 13 14 15 16 17 18 

się dwa wskaźniki I i J każdego wskazującego na początku tablic przyrost ì A [i] < B [j]

przyrost j jeżeli A [j]> B [j ]

zrobić to n razy.

liniowe rozwiązanie O (n) O (1).