Search a 2D Matrix II

LeetCode Source

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

1. Integers in each row are sorted in ascending from left to right.
2. Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following 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] ]

Given target = 5, return true.

Given target = 20, return false.

解题思路：O(m + n)解法：

对于2d的矩阵 可以从左下角或者右上角沿着对角线找， 例如从左下角开始找（因为从上到下和从左到右都是递增的）， 如果大于target就网上走一格， 如果小于target就往下走一格

public int searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0){
        return 0;
    }
    if (matrix[0] == null || matrix[0].length == 0){
        return 0;
    }

    int row = matrix.length - 1;
    int column = matrix[0].length - 1;
    int m = row;
    int n = 0;
    int count = 0;
    while (m >= 0 && m <= row && n >= 0 && n <= column){
        int cur = matrix[m][n];
        if (cur == target){
            count++;
            m--;
        } else if (cur > target){
            m--;
        } else {
            n++;
        }
    }
    return count;
}

References

1 Search a 2D Matrix II