74. Search a 2D Matrix

三刷 06/2022

还可以binary search from 0 to MN - 1，然后计算row=mid / cols, col = mid % cols

Version #1 Binary Search for rows and columns

Time O(logM + logN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search a 2D Matrix.

Memory Usage: 43 MB, less than 29.40% of Java online submissions for Search a 2D Matrix.

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {

        int start = 0, end = matrix.length - 1;

        // find the last row whose first element <= target

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (matrix[mid][0] == target) {

                return true;

            }

            if (matrix[mid][0] < target) {

                start = mid;

            } else {

                end = mid - 1;

            }

        }

        int row = start;

        if (matrix[end][0] <= target) {

            row = end;

        }

        // search in the row for the target

        start = 0;

        end = matrix[0].length - 1;

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (matrix[row][mid] == target) {

                return true;

            }

            if (matrix[row][mid] < target) {

                start = mid + 1;

            } else {

                end = mid - 1;

            }

        }

        return matrix[row][start] == target;

    }

}

二刷
Version #1 Flatten the matrix
Treat the matrix as a sorted list
O(log(mn)) = O(log(m) + log(n)), which is exactly the same as first searching for the row, then searching inside the row.

class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) { return false; } int rows = matrix.length; int cols = matrix[0].length; int start = 0; int end = rows * cols - 1; while (start < end) { int mid = start + (end - start) / 2; if (matrix[mid / cols][mid % cols] == target) { return true; } else if (matrix[mid / cols][mid % cols] > target) { end = mid - 1; } else { start = mid + 1; } } return matrix[start / cols][start % cols] == target; } }


Version #2 Binary Search vertically and horizontally
不好的版本
6.57 %
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) { return false; } int width = matrix[0].length; int rowStart = 0; int rowEnd = matrix.length - 1; int row = 0; while (rowStart < rowEnd) { row = rowStart + (rowEnd - rowStart) / 2; if (matrix[row][0] <= target && matrix[row][width - 1] >= target) { rowStart = row; break; } else if (matrix[row][0] > target) { rowEnd = row - 1; } else { rowStart = row + 1; } } row = rowStart; int start = 0; int end = width - 1; while (start < end) { int mid = start + (end - start) / 2; if (matrix[row][mid] == target) { return true; } else if (matrix[row][mid] < target) { start = mid + 1; } else { end = mid - 1; } } return matrix[row][start] == target; } }

一刷
Version #1

public class Solution {

   public boolean searchMatrix(int[][] matrix, int target) {

if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {

return false;

}

int rows = matrix.length;

int cols = matrix[0].length;

int start = 0;

int end = rows * cols - 1;

int mid = 0;

while (start <= end) {

mid = start + (end - start) / 2;

int x = mid / cols;

   int y = mid % cols;

if (matrix[x][y] == target) {

return true;

} else if (matrix[x][y] > target) {

end = mid - 1;

} else {

start = mid + 1;

}

}

return false;

   }

}