[LintCode] 38 Search a 2D Matrix II 解题报告

Description
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


思路
这题左上角是最小的点，右下角是最大的点，每一行递增，每一列递减。
我们可以从左下角开始找。
如果candidate > target，说明这一行都不用看了，上面可能会有target。我们往上走。
如果candidate < target，说明这一列都不用看了，右边可能会有target。我们往右走。
如果candidate == target，说明这一行和这一列都不用看了，我们往右上移动一格接着找。


Code

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] == null || matrix[0].length == 0) {
            return 0;
        }
        
        int N = matrix.length;
        int M = matrix[0].length;
        
        int i = N - 1;
        int j = 0;
        int count = 0;
        while (i >= 0 && j < M) {
            if (matrix[i][j] > target) {
                i--;
            }
            else if (matrix[i][j] < target) {
                j++;
            }
            else {
                count++;
                i--;
                j++;
            }
        }
        
        return count;
    }
}