240. Search a 2D Matrix II

Leetcode

https://leetcode.com/problems/search-a-2d-matrix-ii/

題目

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.

• Integers in each column are sorted in ascending from top to bottom.

解答

• 方法一

先用 binary search 找出小於 target 並且最接近其的 row, col 位置，再依序往右、往上尋找 target 是否存在

var searchMatrix = function (matrix, target) {
  const m = matrix.length;
  const n = matrix[0].length;
  const binarySearch = () => {
    let startRow = 0;
    let endRow = m - 1;
    while (startRow < endRow) {
      const mid = Math.ceil((startRow + endRow) / 2);
      if (matrix[mid][0] <= target) {
        startRow = mid;
      } else {
        endRow = mid - 1;
      }
    }

    let startCol = 0;
    let endCol = n - 1;
    while (startCol < endCol) {
      const mid = Math.ceil((startCol + endCol) / 2);
      if (matrix[startRow][mid] <= target) {
        startCol = mid;
      } else {
        endCol = mid - 1;
      }
    }
    return {
      row: startRow,
      col: startCol
    };
  };

  let { row, col } = binarySearch();
  while (row >= 0 && col < n) {
    if (matrix[row][col] === target) return true;
    if (matrix[row][col] < target) col++;
    if (matrix[row][col] > target) row--;
  }
  return false;
};

Runtime: 724 ms, faster than 49.85% of JavaScript online submissions for Search a 2D Matrix II.

Memory Usage: 43.8 MB, less than 11.52% of JavaScript online submissions for Search a 2D Matrix II.

• 方法二

單純由左下角開始，往右往上尋找 target 是否存在

var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    let row = m - 1;
    let col = 0;
    while(row>=0 && col<n) {
        if(matrix[row][col] === target) return true;
        if(matrix[row][col] < target) col++;
        else if(matrix[row][col] > target) row--;
    }
    return false;
};

Runtime: 579 ms, faster than 59.77% of JavaScript online submissions for Search a 2D Matrix II.

Memory Usage: 41.6 MB, less than 93.29% of JavaScript online submissions for Search a 2D Matrix II.

測資

let matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20;
matrix = [[-1,3]], target=3;

console.log(searchMatrix(matrix, target));

參考資料

1. https://anj910.medium.com/leetcode-240-search-a-2d-matrix-ii-%E4%B8%AD%E6%96%87-fa800c03adf7