74. Search a 2D Matrix - Medium

前往題目

想法

• 之前做過，題目要求O(log(m * n))以為不能疊代整個矩陣，於是先用binary search尋找target可能在哪一行，然後再搜尋特定那一行
• 看了之前我的submission才發現其實可以，因為都用binary search所以每行都檢查的話就符合題目要求的time complexity

思路

1. 疊代每行
2. 在每行binary search target

Code

$O(mlogn)$

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        final int M = matrix.length;
        final int N = matrix[0].length;

        for (int row = 0; row < M; ++row) {
            int l = 0, r = N - 1;

            while (l <= r) {
                int mid = l + (r - l) / 2;

                if (matrix[row][mid] == target) {
                    return true;
                } else if (matrix[row][mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }

        return false;
    }
}

2025/04/21

• 以下方法更快：$O(log(mn))$
• 直接把整個 matrix 當作陣列來看，就可以實施一般的二元搜尋

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        final int ROWS = matrix.length, COLS = matrix[0].length;

        int l = 0, r = ROWS * COLS - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            int row = mid / COLS, col = mid % COLS;
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
}