Przeszukiwanie tablicy 2D w czasie sublinear

to problem z ostatnich kodowania wywiadziePrzeszukiwanie tablicy 2D w czasie sublinear

Dodaj skuteczny algorytm wyszukuje wartość w MxN matrycy.

Macierz ta posiada następujące właściwości:

Liczby w każdym rzędzie są sortowane w porządku rosnącym, od lewej do prawej.

Liczba całkowita w każdej kolumnie jest posortowana rosnąco od góry do dołu.
.

[1, 4, 7, 11, 15] 

    [2, 5, 8, 12, 19] 

    [3, 6, 9, 16, 22] 

    [10, 13, 14, 17, 24] 

    [18, 21, 23, 26, 30]

Czy istnieje sposób, aby to zrobić poniżej O (mn). Nie widzę, jak można wykonać wyszukiwanie binarne w tej tablicy, ponieważ nie ma sposobu na wyeliminowanie czegokolwiek.

Źródło

2016-04-23 Zeus

Sądzę, że można wykonać wyszukiwanie binarne w każdym rzędzie. Będzie to O (m * log (n)). – marstran

To jest poprawa. – Zeus

Każdy wiersz jest zbędny. Zauważ, że w każdej submacie, dolny prawy element jest maksymalny. W ten sposób można na przykład przemieścić główną przekątną, aby znaleźć pierwszą wartość V wyższą niż wzorzec wyszukiwania. Wzorzec wyszukiwania powinien znajdować się gdzieś w uzupełnieniu do kwadratowej submatrix od lewego górnego rogu do V. – bipll

Można w ten prosty algorytm, który wykorzystuje fakt, że w matrycy z tych właściwości, wartość mtx[i][j] jest zawsze mniejsza niż wartość mtx[x][y], gdzie x > i lub y > j, innymi słowy, każda wartość w prawo i dół:

public static boolean find(int[][] mtx, int val) { 
    int maxCol = mtx[0].length, minCol = 0; 

    for(int i = 0 ; i < mtx.length ; i++) { 
     for(int j = minCol ; j < maxCol ; j++) { 
      if(val == mtx[i][j]) return true; 

      if(val < mtx[i][j]) { 
       maxCol = j; 
       break; 
      } 
     } 

     if(maxCol == 0) break; 

     minCol = 0; 
     if(i != mtx.length-1 && val > mtx[i+1][maxCol-1]) minCol = maxCol-1; 
    } 

    return false; 
}

Chodzi o to, aby szukać wiersz po wierszu, a jeśli okaże się, że wartość jest większa, można przestać patrzeć w tym samym wierszu i wiesz, że nie trzeba szukać poza tym w kolumnie przyszłe rzędy. A jeśli pierwsza wartość wiersza jest większa niż wartość, możesz zatrzymać wyszukiwanie i zwrócić fałsz. Ponadto, na końcu wyszukiwania każdego wiersza, sprawdzasz komórkę od następnego wiersza pod maxCol-1, jeśli wartość jest większa, to w następnym cyklu możesz pominąć każdą poprzednią komórkę.

Najgorszy scenariusz to największa wartość (lub większa), a złożoność to O (m + n), ponieważ sprawdziłaby cały pierwszy wiersz, a następnie pominie następne m wierszy.

Źródło

2016-04-23 20:13:50 Maljam

Niezły pomysł, ale czy to jeszcze nie jest O (n)? Jeśli zdarzy ci się znaleźć największą wartość, będziesz musiał przejrzeć wszystkie wartości, prawda? – marstran

@marstran dobry punkt, myślę, że mógłbym go jeszcze poprawić, w jakiś sposób scalając go z "symetrycznym algotritmem", gdzie zaczynałbyś w przeciwległym rogu. Pomyślę o tym .. – Maljam

@marstran Zmieniłem trochę algorytm , teraz powinien być sub-liniowy. Czy sie zgadzasz? – Maljam

Dla danej wartości x, granica wędruje przez macierz, mniej więcej od dolnego lewego do prawego górnego, zawsze postępując w prawo lub w górę, i oddzielając wartości większe od x od wartości mniejszych lub równych x.

Rozpocznij od górnego lewego i wyszukaj w dół i w prawo, w prostej linii po przekątnej, aż zostanie znaleziona poszarpana granica. (Jeśli pierwsza krawędź macierzy zostanie osiągnięta, po prostu idź wzdłuż tej granicy w prawo lub w dół, kontynuując wyszukiwanie.) Następnie przejdź wzdłuż granicy w obu kierunkach, aż zostanie znalezione x lub nie ma już komórek macierzy do przeszukania.

Wyszukiwanie może obejmować trzy sekcje ścieżki, z których każda działa tylko w prawo-w dół, w prawo iw górę lub w lewo i w dół. Takie długości ścieżek wynoszą O (m + n). Zatem całe wyszukiwanie to O (m + n).

Źródło

2016-04-23 20:44:06 mjwach

Przeszukiwanie tablicy 2D w czasie sublinear

Odpowiedz

Powiązane problemy