Search a 2D Matrix
Du erhältst ein Gitter aus Ganzzahlen matrix mit m Zeilen und n Spalten sowie eine Ganzzahl target. Jede Zeile ist aufsteigend sortiert, und der erste Wert jeder Zeile ist größer als der letzte Wert der darüberliegenden Zeile. Gib true zurück, wenn target im Gitter vorkommt, andernfalls false, und zwar in O(log(m × n)) Zeit.
Funktion
- matrixinteger-2d-array
- das Raster, als Liste von Zeilen angegeben, zeilenweise sortiert
- targetinteger
- der zu suchende Wert
- Gibt zurückboolean
- wahr, wenn sich das Ziel im Raster befindet, andernfalls falsch
Einschränkungen
1 ≤ m, n ≤ 100, wobeim = matrix.lengthundn = matrix[i].length- Jede Zeile hat dieselbe Länge
n. -104 ≤ matrix[i][j], target ≤ 104- Jede Zeile ist streng aufsteigend sortiert, und der erste Wert jeder Zeile ist größer als der letzte Wert der vorherigen Zeile.
Beispiele
- Eingabe
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Ausgabe
- true
- Erklärung
- Zeilenweise gelesen bilden die 12 Werte eine sortierte Liste. Bei einer binären Suche über die Positionen 0 bis 11 wird 21 an Position 5 geprüft (zu klein), 33 an Position 8 (zu groß), dann wird 26 an Position 6 gefunden.
- Eingabe
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Ausgabe
- false
- Erklärung
- 16 käme nach 14, dem letzten Wert in Zeile 0, und vor 17, dem ersten Wert in Zeile 1. Dazwischen liegt nichts, also befindet sich 16 nicht im Raster.
Weiterführende Frage
Angenommen, die Zeilen könnten unterschiedlich lang sein und wären trotzdem durchgehend sortiert. Wie würdest du eine Position in eine Zeile und eine Spalte umwandeln, und wie hoch wären die Suchkosten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Lies die Matrix Zeile für Zeile von links nach rechts, als wäre sie eine lange Liste. Was fällt dir an der Reihenfolge der Werte in dieser Liste auf?
Zusammen bedeuten die beiden Regeln, dass die gesamte Matrix, zeilenweise gelesen, eine einzige sortierte Liste mit
m × nWerten ist. Du kannst darin eine binäre Suche durchführen, ohne sie jemals aufzubauen.Binäre Suche über die Positionen
0bism × n - 1. Die Positionpliegt in Zeilep / nund Spaltep % n(Ganzzahldivision), sodass jeder Schritt eine Zelle liest und die Hälfte der verbleibenden Positionen verwirft.
Lösung
Die beiden Sortierregeln machen das Raster zusammen, zeilenweise gelesen, zu einer einzigen sortierten Liste mit m × n Werten. Durchsuche diese Liste binär nach der Position und wandle jede Position mit einer Division wieder in eine Zeile und eine Spalte um. Ein Raster mit 100 mal 100 Feldern benötigt dann höchstens 14 Vergleiche statt 10000.
Überprüfe jede Zelle
Idee
Vergleiche jede Zelle mit target und gib bei einer Übereinstimmung true zurück, nach der letzten Zelle false. Dabei wird jede Zelle gelesen, daher ist das Verfahren für jedes Raster korrekt, ob sortiert oder nicht. Die Reihenfolge wird nie verwendet, daher erfordert ein Raster mit 100 mal 100 Zellen bis zu 10000 Vergleiche.
Algorithmus
- Gehe jede Zeile von
matrixdurch und betrachte jeden Wert der Reihe nach. - Wenn der Wert gleich
targetist, gibtruezurück. - Gib nach den Schleifen
falsezurück.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseGehe von der oberen rechten Ecke aus
Idee
Von der Zelle oben rechts aus ist jeder Wert links davon kleiner und jeder Wert darunter größer. Ist die Zelle größer als target, ist auch die Spalte darunter größer: Gehe nach links und schließe diese Spalte aus. Ist sie kleiner, ist auch die Zeile links davon kleiner: Gehe nach unten und schließe diese Zeile aus.
Im ersten Beispiel ist 14 kleiner als 26, also gehe nach unten zu 30. 30 ist größer, also gehe nach links zu 26 – ein Treffer. Jeder Schritt entfernt eine Zeile oder eine Spalte, also brauchst du höchstens m + n Schritte: 200 bei einem 100-mal-100-Raster. Für diesen Suchweg müssen nur die Zeilen und Spalten sortiert sein; daher nutzt er nur die Hälfte dessen, was dieses Raster bietet.
Algorithmus
- Beginne in Zeile
0und in der letzten Spalte. - Solange sich die Zeile und die Spalte innerhalb des Rasters befinden, lies die Zelle aus.
- Wenn sie gleich
targetist, gibtruezurück. - Wenn sie größer ist, gehe eine Spalte nach links; wenn sie kleiner ist, gehe eine Zeile nach unten.
- Wenn du das Raster verlässt, gib
falsezurück.
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 FalseBinäre Suche im abgeflachten Raster
Idee
Nummeriere die Zellen zeilenweise: Zeile 0 enthält die Positionen 0 bis n - 1, Zeile 1 enthält n bis 2n - 1 und so weiter. Jede Zeile ist sortiert und beginnt oberhalb der Stelle, an der die vorherige Zeile endete, daher steigen die Werte mit der Position immer weiter an. Das ist eine sortierte Liste, auf die die binäre Suche angewendet werden kann.
Du erstellst die Liste nie. Position p befindet sich in Zeile p / n und Spalte p % n, wobei ganzzahlig dividiert wird. Im ersten Beispiel gilt n = 4, also befindet sich Position 6 in Zeile 1, Spalte 2, wo der Wert 26 steht. Jeder Vergleich halbiert die Positionen, an denen sich target befinden könnte: bei 10000 Zellen höchstens 14, mit zwei Indizes zusätzlichem Speicher.
Algorithmus
- Seien
mundndie Anzahl der Zeilen und Spalten, und setzelo = 0,hi = m × n - 1. - Solange
lo ≤ higilt, nimmmidals Mittelpunkt zwischen ihnen. - Lies
value = matrix[mid / n][mid % n]. - Wenn
valuegleichtargetist, gibtruezurück. Wenn es kleiner ist, setzelo = mid + 1; andernfalls setzehi = mid - 1. - Wenn die Schleife endet, gib
falsezurück.
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
Stolperfallen und Grenzfälle
- Durch Division durch die Anzahl der Zeilen statt der Spalten. Position
pbefindet sich in Zeilep / n; mitman dieser Stelle funktioniert der Code auf quadratischen Gittern, schlägt aber bei 3 Zeilen und 4 Spalten fehl. - In der Version mit zwei Suchvorgängen wird nicht berücksichtigt, dass
targetkleiner alsmatrix[0][0]ist. Keine Zeile beginnt bei diesem Wert oder darunter, und ein Zeilenindex von-1gelangt zur zweiten Suche. - Eine Schleife mit
lo < hibei einem inklusivenhi. Ein 1-mal-1-Gitter, dastargetenthält, gibtfalsezurück, weil die Schleife nie ausgeführt wird. - In Lua und R wird die Umstellung auf 1-basierte Indizes vergessen: Position
pist Zeilep / n + 1, Spaltep % n + 1.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität der Suche in einer 2D-Matrix?
Die binäre Suche über das abgeflachte Raster benötigt O(log(m × n)) Zeit und O(1) Speicherplatz: höchstens 14 Vergleiche für 10000 Zellen. Da log(m × n) = log m + log n, entspricht sie der Suche nach der Zeile und anschließend innerhalb dieser Zeile.
Solltest du den Weg über die obere rechte Ecke oder die binäre Suche verwenden?
Der Ecklauf benötigt O(m + n) Schritte und setzt nur voraus, dass Zeilen und Spalten sortiert sind. Daher löst er auch die Variante, bei der eine Zeile unterhalb des Endes der darüberliegenden Zeile beginnen kann. Wenn jede Zeile oberhalb des Endes der vorherigen beginnt, wie hier, ist die binäre Suche schneller.
Ist es auch korrekt, zwei binäre Suchen durchzuführen: eine für die Zeile und eine innerhalb der Zeile?
Ja. Durchsuche die erste Spalte binär nach der letzten Zeile, deren erster Wert höchstens target ist, und durchsuche dann diese Zeile binär. Das läuft in O(log m + log n), also mit derselben Laufzeit. Die einzelne Suche erledigt dieselbe Arbeit mit einer Schleife und weniger Sonderfällen.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def searchMatrix(matrix, target):
# Schreibe hier den CodeTest #1
Test #2
Argumente
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Erwartete Ausgabe
true