240. Search a 2D Matrix II

harry xie
2024-10-13 12:07:52

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 度，並把每個元素看做節點，那就變成類似二元搜尋樹的形式:

240. 搜索二维矩阵 II（贪心，清晰图解）

從矩陣右上角當作樹的根節點，往左數字變小，往下數字變大，

所以用 target 和當前值比較，若 target 較大，往下移動，若 target 較小，往左移動，

相等返回 true

解法的時間空間複雜度

時間複雜度: O(m + n)，矩陣行列數
空間複雜度: O(1)