Search a 2D Matrix II 38

Question

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

Integers in each row are sorted from left to right.

Integers in each column are sorted from up to bottom.

No duplicate integers in each row or column.

Example

Consider the following matrix:

[ [1, 3, 5, 7], [2, 4, 7, 8], [3, 5, 9, 10] ]

Given target = 3, return 2.

Challenge

O(m+n) time and O(1) extra space

Solution

从左下角开始向右上角搜索，若当前元素比target小则向右，大则向上，相等则向右上。这样最多走m＋n步，所以时间复杂度为O(m+n)。

代码如下：

public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param: A number you want to search in the matrix
     * @return: An integer indicate the occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        // write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }

        int x = matrix.length - 1;
        int y = 0;
        int count = 0;

        while(x >= 0 && y < matrix[0].length){
            if(matrix[x][y] == target){
                count++;
                x--;
                y++;
            }else if(matrix[x][y] < target){
                y++;
            }else{
                x--;
            }
        }

        return count;
    }
}