Search a 2D Matrix

Q: Jaka jest złożoność czasowa wyszukiwania w macierzy 2D?

Wyszukiwanie binarne w spłaszczonej siatce działa w czasie O(log(m × n)) i używa O(1) pamięci: dla 10000 komórek wymaga najwyżej 14 porównań. Ponieważ log(m × n) = log m + log n , jest równoważne wyszukiwaniu wiersza, a następnie elementu w tym wierszu.

Q: Czy użyć marszu od prawego górnego rogu, czy wyszukiwania binarnego?

Przejście po narożnikach wymaga O(m + n) kroków i zakłada jedynie, że wiersze i kolumny są posortowane, więc rozwiązuje również wariant, w którym wiersz może zaczynać się poniżej końca wiersza powyżej. Gdy każdy wiersz zaczyna się powyżej miejsca, w którym kończy się poprzedni, jak tutaj, wyszukiwanie binarne jest szybsze.

Q: Czy dwa wyszukiwania binarne — jedno dla wiersza, a drugie w jego obrębie — również są poprawne?

Tak. Wyszukaj binarnie w pierwszej kolumnie ostatni wiersz, którego pierwsza wartość jest nie większa niż target , a następnie wyszukaj binarnie w tym wierszu. Złożoność wynosi O(log m + log n) , czyli tyle samo. Pojedyncze wyszukiwanie wykonuje tę samą pracę przy użyciu jednej pętli i mniejszej liczby przypadków brzegowych.

ŚrednieWyszukiwanie binarne

+10

Otrzymujesz siatkę liczb całkowitych matrix o m wierszach i n kolumnach oraz liczbę całkowitą target. Każdy wiersz jest posortowany rosnąco, a pierwsza wartość w każdym wierszu jest większa od ostatniej wartości w wierszu powyżej. Zwróć true, jeśli target znajduje się w siatce, a w przeciwnym razie false, w czasie O(log(m × n)).

Funkcja

searchMatrix(matrix: integer-2d-array, target: integer) → boolean

matrixinteger-2d-array: siatka, podana jako lista wierszy, uporządkowana wiersz po wierszu
targetinteger: wartość, której należy szukać
Zwracaboolean: true, jeśli target znajduje się w siatce, w przeciwnym razie false

Ograniczenia

1 ≤ m, n ≤ 100, gdzie m = matrix.length i n = matrix[i].length
Każdy wiersz ma tę samą długość n.
-10⁴ ≤ matrix[i][j], target ≤ 10⁴
Każdy wiersz jest uporządkowany ściśle rosnąco, a pierwsza wartość każdego wiersza jest większa od ostatniej wartości poprzedniego wiersza.

Przykłady

Wejście: matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
Wyjście: true
Wyjaśnienie: Czytając wiersz po wierszu, 12 wartości tworzy jedną posortowaną listę. Wyszukiwanie binarne na pozycjach od 0 do 11 sprawdza 21 na pozycji 5 (za mała), 33 na pozycji 8 (za duża), a następnie znajduje 26 na pozycji 6.

Pytanie dodatkowe

Załóżmy, że wiersze mogą mieć różną długość, ale nadal są posortowane od początku do końca. Jak zamienić pozycję na wiersz i kolumnę oraz jaki byłby koszt wyszukiwania?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Obie reguły porządkowania sprawiają, że siatka, odczytywana wiersz po wierszu, tworzy jedną posortowaną listę m × n wartości. Wykonaj wyszukiwanie binarne na tej liście według pozycji, a następnie przekształć każdą pozycję z powrotem w wiersz i kolumnę za pomocą jednego dzielenia. Siatka o wymiarach 100 na 100 wymaga wtedy najwyżej 14 porównań zamiast 10000.

Sprawdź każdą komórkę

Intuicja

Porównaj każdą komórkę z target i zwróć true w przypadku dopasowania, a false po sprawdzeniu ostatniej komórki. Odczytuje każdą komórkę, więc działa poprawnie dla każdej siatki, posortowanej lub nie. Nie wykorzystuje kolejności, więc siatka 100 na 100 wymaga maksymalnie 10000 porównań.

Algorytm

Dla każdego wiersza matrix sprawdzaj kolejno każdą wartość.
Jeśli wartość jest równa target, zwróć true.
Po pętlach zwróć false.

def searchMatrix(matrix, target):
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

Idź od prawego górnego rogu

Intuicja

Zaczynając od komórki w prawym górnym rogu, każda wartość po lewej stronie jest mniejsza, a każda wartość poniżej jest większa. Jeśli wartość w komórce jest większa niż target, to kolumna poniżej niej również jest większa: przejdź w lewo i wyeliminuj tę kolumnę. Jeśli jest mniejsza, to wiersz po jej lewej stronie również jest mniejszy: przejdź w dół i wyeliminuj ten wiersz.

W pierwszym przykładzie 14 jest mniejsze niż 26, więc przejdź w dół do 30. 30 jest większe, więc przejdź w lewo do 26 — to szukana wartość. Każdy krok eliminuje wiersz lub kolumnę, więc wykonasz najwyżej m + n kroków: 200 w siatce o wymiarach 100 na 100. Wystarczy, że wiersze i kolumny są posortowane, więc to podejście nie wykorzystuje połowy informacji, jakie daje ta siatka.

Algorytm

Zacznij od wiersza 0 i ostatniej kolumny.
Gdy wiersz i kolumna znajdują się w siatce, odczytaj komórkę.
Jeśli jest równa target, zwróć true.
Jeśli jest większa, przesuń się o jedną kolumnę w lewo; jeśli jest mniejsza, przesuń się o jeden wiersz w dół.
Gdy wyjdziesz poza siatkę, zwróć false.

def searchMatrix(matrix, target):
    # Start at the top-right corner: left is smaller, down is larger.
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        value = matrix[r][c]
        if value == target:
            return True
        if value > target:
            c -= 1  # every value below in this column is larger still
        else:
            r += 1  # every value to the left in this row is smaller still
    return False

Wyszukiwanie binarne w spłaszczonej siatce

Intuicja

Ponumeruj komórki wierszami: wiersz 0 zawiera pozycje od 0 do n - 1, wiersz 1 zawiera pozycje od n do 2n - 1 i tak dalej. Każdy wiersz jest posortowany i zaczyna się powyżej miejsca, w którym kończył się poprzedni wiersz, więc wartości rosną wraz z pozycją. To posortowana lista, do której można zastosować wyszukiwanie binarne.

Nie tworzysz listy. Pozycja p znajduje się w wierszu p / n i kolumnie p % n, przy użyciu dzielenia całkowitego. W pierwszym przykładzie n = 4, więc pozycja 6 to wiersz 1, kolumna 2, która zawiera 26. Każde porównanie zmniejsza o połowę liczbę pozycji, w których może znajdować się target: dla 10000 komórek potrzeba najwyżej 14 porównań i dwóch indeksów dodatkowej pamięci.

Algorytm

Niech m i n oznaczają liczbę wierszy i kolumn, a lo = 0, hi = m × n - 1.
Dopóki lo ≤ hi, wybierz mid pośrodku między nimi.
Odczytaj value = matrix[mid / n][mid % n].
Jeśli value jest równe target, zwróć true. Jeśli jest mniejsze, ustaw lo = mid + 1; w przeciwnym razie ustaw hi = mid - 1.
Po zakończeniu pętli zwróć false.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    # Read row by row, the cells form one sorted list of rows * cols values.
    # Position p of that list is matrix[p // cols][p % cols].
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Pułapki i przypadki brzegowe

Dzielenie przez liczbę wierszy zamiast kolumn. Pozycja p znajduje się w wierszu p / n; gdy w jej miejsce użyjesz m, kod działa dla kwadratowych siatek, ale zawodzi dla siatki z 3 wierszami i 4 kolumnami.
W wersji z dwoma wyszukiwaniami brak obsługi sytuacji, gdy target jest mniejszy niż matrix[0][0]. Żaden wiersz nie zaczyna się od tej wartości ani od mniejszej, a indeks wiersza -1 trafia do drugiego wyszukiwania.
Używanie pętli z warunkiem lo < hi przy włącznie uwzględnionym hi. Siatka 1 na 1 zawierająca target zwraca false, ponieważ pętla nigdy się nie wykonuje.
W Lua i R zapomnienie o przesunięciu indeksów do numeracji od 1: pozycja p to wiersz p / n + 1, kolumna p % n + 1.

Najczęstsze pytania3

Jaka jest złożoność czasowa wyszukiwania w macierzy 2D?

Wyszukiwanie binarne w spłaszczonej siatce działa w czasie O(log(m × n)) i używa O(1) pamięci: dla 10000 komórek wymaga najwyżej 14 porównań. Ponieważ log(m × n) = log m + log n, jest równoważne wyszukiwaniu wiersza, a następnie elementu w tym wierszu.

Czy użyć marszu od prawego górnego rogu, czy wyszukiwania binarnego?

Przejście po narożnikach wymaga O(m + n) kroków i zakłada jedynie, że wiersze i kolumny są posortowane, więc rozwiązuje również wariant, w którym wiersz może zaczynać się poniżej końca wiersza powyżej. Gdy każdy wiersz zaczyna się powyżej miejsca, w którym kończy się poprzedni, jak tutaj, wyszukiwanie binarne jest szybsze.

Czy dwa wyszukiwania binarne — jedno dla wiersza, a drugie w jego obrębie — również są poprawne?

Tak. Wyszukaj binarnie w pierwszej kolumnie ostatni wiersz, którego pierwsza wartość jest nie większa niż target, a następnie wyszukaj binarnie w tym wierszu. Złożoność wynosi O(log m + log n), czyli tyle samo. Pojedyncze wyszukiwanie wykonuje tę samą pracę przy użyciu jednej pętli i mniejszej liczby przypadków brzegowych.

def searchMatrix(matrix, target):
    # Wpisz kod tutaj

Test #1

Test #2

Argumenty

matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]
target = 26

Oczekiwany wynik

true

Search a 2D Matrix

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdą komórkę

Idź od prawego górnego rogu

Wyszukiwanie binarne w spłaszczonej siatce

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania