iT邦幫忙

2024 iThome 鐵人賽

DAY 29
0
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)

Yes


上一篇
678. Valid Parenthesis String
下一篇
2013. Detect Squares
系列文
向 NeetCode、官神看齊! 分享自己的解題筆記和影片。30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言