題目網址：https://leetcode.cn/problems/search-a-2d-matrix-ii/

題意：設計一高效演算法來搜索 m x n matrix 中是否存在整數 target, matrix 滿足以下特性:

  • 每行的元素由上到下按升序排列
  • 每列的元素由左到右按升序排列

Solution 1：

想法：對每一列做 Binary Search, 判斷 target 是否在該列中，從而判斷 target 是否出現

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        const int m = matrix.size(), n = matrix[0].size();

        for (int row = 0; row < m; ++row) {
            int left = 0, right = n;

            while (left < right) {
                const int mid = left + (right - left) / 2;

                if (matrix[row][mid] >= target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            // 當 matrix 中所有的元素都比 target 小 (target 不存在), left 會越界
            // 所以在存取 matrix[row][left] 前, 要先判斷 left 是否越界, 否則存取會出錯
            if (left < n && matrix[row][left] == target) {
                return true;
            }
        }

        return false; // not found

    }
};
  • time：$O(m \cdot log(n))$ ➔ 對每一列做 Binary Search
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：利用 Z 字形搜索, 從 matrix 右上角(左下角也行)開始

  • 若 matrix[row][col] == target : 則 return true

  • 若 matrix[row][col] > target : 則代表 matrix[row ~ m][col] 都比 target 大, 故 col - 1

  • 若 matrix[row][col] < target : 則代表 matrix[row][col ~ n] 都比 target 小, 故 row + 1

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        const int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;

        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                ++row;
            } else {
                --col;
            }
        }

        return false; // not found
    }
};
  • time：$O(m + n)$ ➔ 在搜索的過程中，如果我們沒有找到target, 那麼我們要馬將 y - 1, 要馬將 x + 1。由於 (x, y) 的初始值為 (0, n - 1), 因此是 y 最多能被減少 n 次, x 最多能被增加 m 次, 總搜索次數為 m + n
  • space：$O(1)$ ➔ 只需常數空間