Dies ist ein Problem aus einem kürzlichen Coding-Interview
Schreiben Sie einen effizienten Algorithmus, der nach einem Wert in einer m x n -Matrix sucht.
Diese Matrix hat die folgenden Eigenschaften:
Ganzzahlen in jeder Zeile sind aufsteigend von links nach rechts sortiert.
Ganzzahlen in jeder Spalte sind von oben nach unten aufsteigend sortiert.
.
Gibt es einen Weg, dies unter O (mn) zu tun. Ich kann nicht sehen, wie man eine binäre Suche auf diesem Array durchführen kann, da es keine Möglichkeit gibt, etwas zu eliminieren.
Sie können diesen einfachen Algorithmus verwenden, der die Tatsache ausnutzt, dass in einer Matrix mit diesen Eigenschaften der Wert mtx[i][j] immer kleiner ist als jeder Wert mtx[x][y] , wobei x > i oder y > j , mit anderen Worten, ein beliebiger Wert rechts und unten:
Die Idee besteht darin, Zeile für Zeile zu suchen, und wenn Sie einen Wert finden, der größer ist, können Sie aufhören, in dieser Zeile zu suchen, und Sie wissen, dass Sie in späteren Zeilen nicht über diese Spalte hinaus suchen müssen. Und wenn der erste Wert einer Zeile größer als der Wert ist, können Sie die Suche stoppen und false zurückgeben. Außerdem suchen Sie am Ende jeder Zeilensuche die Zelle aus der nächsten Zeile bei maxCol-1 . Wenn der Wert größer ist, können Sie im nächsten Zyklus jede vorangehende Zelle überspringen.
Das Worst-Case-Szenario ist der größte Wert (oder größer), und die Komplexität ist O (m + n), weil es die gesamte erste Zeile überprüft und dann die nächsten m Zeilen überspringt.
Für einen gegebenen Wert x gibt es eine Grenze, die durch die Matrix läuft, mehr oder weniger von links unten nach rechts oben, immer nach rechts oder oben gehend, und Werte, die größer als x sind, von Werten kleiner oder gleich x trennen .
Beginnen Sie von oben links und suchen Sie nach unten und rechts in einer geraden diagonalen Linie, bis diese gezackte Grenze gefunden wird. (Wenn ein Rahmen der Matrix zuerst erreicht wird, folgen Sie einfach diesem Rahmen nach rechts oder unten und setzen die Suche fort.) Dann gehen Sie entlang der Grenze in beide Richtungen, bis x gefunden wird oder keine Matrixzellen mehr zu suchen sind.
Diese Suche kann drei Pfadabschnitte durchlaufen, von denen jeder nur nach rechts unten, rechts nach oben oder links nach unten verläuft. Die Längen dieser Pfade sind O (m + n). Also ist die ganze Suche O (m + n).