Search a 2D Matrix
Ti viene fornita una griglia di numeri interi matrix con m righe e n colonne e un numero intero target. Ogni riga è ordinata in ordine crescente e il primo valore di ogni riga è maggiore dell’ultimo valore della riga precedente. Restituisci true se target compare nella griglia e false altrimenti, in tempo O(log(m × n)).
Funzione
- matrixinteger-2d-array
- la griglia, fornita come elenco di righe, ordinate riga per riga
- targetinteger
- il valore da cercare
- Restituisceboolean
- true se il target è nella griglia, false altrimenti
Vincoli
1 ≤ m, n ≤ 100, dovem = matrix.lengthen = matrix[i].length- Ogni riga ha la stessa lunghezza
n. -104 ≤ matrix[i][j], target ≤ 104- Ogni riga è ordinata in ordine strettamente crescente e il primo valore di ogni riga è maggiore dell'ultimo valore della riga precedente.
Esempi
- Input
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Output
- true
- Spiegazione
- Leggendo riga per riga, i 12 valori formano un'unica lista ordinata. Una ricerca binaria nelle posizioni da 0 a 11 controlla 21 alla posizione 5 (troppo piccolo), 33 alla posizione 8 (troppo grande), poi trova 26 alla posizione 6.
- Input
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Output
- false
- Spiegazione
- 16 verrebbe dopo 14, l’ultimo valore della riga 0, e prima di 17, il primo valore della riga 1. Non c’è nulla tra loro, quindi 16 non è nella griglia.
Per approfondire
Supponiamo che le righe possano avere lunghezze diverse, pur essendo ordinate una di seguito all’altra. Come trasformeresti una posizione in una riga e una colonna, e quale sarebbe il costo della ricerca?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Leggi la matrice riga per riga, da sinistra a destra, come se fosse un'unica lunga lista. Che cosa noti sull'ordine dei valori in quella lista?
Le due regole insieme implicano che l’intera matrice, letta riga per riga, è un’unica lista ordinata di
m × nvalori. Puoi effettuare una ricerca binaria senza mai costruirla.Ricerca binaria sulle posizioni da
0am × n - 1. La posizionepsi trova nella rigap / ne nella colonnap % n(divisione intera), quindi ogni passaggio legge una cella e scarta metà delle posizioni rimanenti.
Soluzione
Le due regole di ordinamento insieme fanno sì che la griglia, letta riga per riga, sia un unico elenco ordinato di valori m × n. Cerca in quell’elenco con la ricerca binaria in base alla posizione e riconverti ogni posizione in una riga e una colonna con una sola divisione. Una griglia di 100 per 100 richiede quindi al massimo 14 confronti invece di 10000.
Controlla ogni cella
Intuizione
Confronta ogni cella con target e restituisci true se trovi una corrispondenza, false dopo l'ultima cella. Legge ogni cella, quindi è corretto per qualsiasi griglia, ordinata o meno. Non sfrutta mai l'ordine, quindi una griglia 100 per 100 richiede fino a 10000 confronti.
Algoritmo
- Per ogni riga di
matrix, esamina ogni valore in ordine. - Se il valore è uguale a
target, restituiscitrue. - Dopo i cicli, restituisci
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseCammina dall'angolo in alto a destra
Intuizione
Dalla cella in alto a destra, ogni valore a sinistra è più piccolo e ogni valore in basso è più grande. Se la cella è più grande di target, anche la colonna sottostante è più grande: spostati a sinistra ed elimina quella colonna. Se è più piccola, anche la riga alla sua sinistra è più piccola: spostati in basso ed elimina quella riga.
Nel primo esempio, 14 è più piccolo di 26, quindi spostati in basso fino a 30. 30 è più grande, quindi spostati a sinistra fino a 26: corrisponde. Ogni passaggio elimina una riga o una colonna, quindi fai al massimo m + n passaggi: 200 per una griglia di 100 per 100. La ricerca richiede solo che le righe e le colonne siano ordinate, quindi ignora metà delle informazioni fornite da questa griglia.
Algoritmo
- Inizia dalla riga
0e dall'ultima colonna. - Mentre la riga e la colonna sono all'interno della griglia, leggi la cella.
- Se è uguale a
target, restituiscitrue. - Se è maggiore, spostati di una colonna a sinistra; se è minore, spostati di una riga verso il basso.
- Quando esci dalla griglia, restituisci
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 FalseRicerca binaria sulla griglia appiattita
Intuizione
Numera le celle riga per riga: la riga 0 contiene le posizioni da 0 a n - 1, la riga 1 contiene da n a 2n - 1 e così via. Ogni riga è ordinata e inizia dopo la fine della riga precedente, quindi i valori aumentano con la posizione. È una lista ordinata e si può applicare la ricerca binaria.
Non costruisci mai la lista. La posizione p si trova nella riga p / n e nella colonna p % n, usando la divisione intera. Nel primo esempio n = 4, quindi la posizione 6 è nella riga 1, colonna 2, che contiene 26. Ogni confronto dimezza le posizioni che potrebbero contenere target: al massimo 14 per 10000 celle, con due indici di memoria aggiuntiva.
Algoritmo
- Siano
menil numero di righe e di colonne, e impostalo = 0,hi = m × n - 1. - Finché
lo ≤ hi, prendimida metà tra loro. - Leggi
value = matrix[mid / n][mid % n]. - Se
valueè uguale atarget, restituiscitrue. Se è più piccolo, impostalo = mid + 1; altrimenti impostahi = mid - 1. - Quando il ciclo termina, restituisci
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
Trappole e casi limite
- Dividere per il numero di righe invece che per quello delle colonne. La posizione
psi trova nella rigap / n; sostituendoman, il codice funziona sulle griglie quadrate e non funziona con 3 righe e 4 colonne. - Nella versione con due ricerche, non gestire
targetquando è minore dimatrix[0][0]. Nessuna riga inizia a quel valore o a uno inferiore, e un indice di riga pari a-1passa alla seconda ricerca. - Eseguire il ciclo con
lo < hiusando unhiinclusivo. Una griglia di 1 per 1 che contienetargetrestituiscefalse, perché il ciclo non viene mai eseguito. - In Lua e R, dimenticare il passaggio agli indici basati su 1: la posizione
pcorrisponde alla rigap / n + 1e alla colonnap % n + 1.
Domande frequenti3
Qual è la complessità temporale di Ricerca in una matrice 2D?
La ricerca binaria sulla griglia appiattita richiede O(log(m × n)) tempo e O(1) spazio: al massimo 14 confronti per 10000 celle. Poiché log(m × n) = log m + log n, equivale a cercare la riga e poi al suo interno.
Devi usare la ricerca nell'angolo in alto a destra o la ricerca binaria?
La ricerca dall'angolo richiede O(m + n) passaggi e necessita solo che le righe e le colonne siano ordinate, quindi risolve anche la variante in cui una riga può iniziare sotto la fine della riga precedente. Quando ogni riga inizia sopra il punto in cui termina la precedente, come in questo caso, la ricerca binaria è più veloce.
Anche due ricerche binarie, una per la riga e una al suo interno, sono corrette?
Sì. Esegui una ricerca binaria sulla prima colonna per trovare l’ultima riga il cui primo valore è al massimo target, quindi esegui una ricerca binaria su quella riga. Ha complessità O(log m + log n), lo stesso limite. La ricerca singola svolge lo stesso lavoro con un ciclo e meno casi limite.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def searchMatrix(matrix, target):
# Scrivi il codice quiTest #1
Test #2
Argomenti
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Output atteso
true