var searchMatrix = function (matrix, target) {
let row = 0;
let col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (target === matrix[row][col]) {
return true;
} else if (target > matrix[row][col]) {
row++;
} else {
col--;
}
}
return false;
};
參考以下解答: 將矩陣轉 45 度,並把每個元素看做節點,那就變成類似二元搜尋樹的形式:
從矩陣右上角當作樹的根節點,往左數字變小,往下數字變大,
所以用 target 和當前值比較,若 target 較大,往下移動,若 target 較小,往左移動,
相等返回 true。
時間複雜度: O(m + n),矩陣行列數
空間複雜度: O(1)