描述

写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。

样例

考虑下列矩阵：

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

给出target = 3，返回 2

思路

本题并不是一道二分法的题，最优的时间复杂度与行列数有关，即O(m+n)；观察矩阵应该从左下角或右上角着手，这样用O(1)的时间就能排除一行一列

代码

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) {
        // check corner case
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        
        // from bottom left to top right
        int n = matrix.length;    // 行
        int m = matrix[0].length; // 列
        int x = n - 1;
        int y = 0;
        int count = 0;
        
        // 从左下角开始，矩阵没有重复元素
        // while 每执行一次，只执行一句 if ，因为上面一句的 if 改变了 x y，下一句 if 如果不重新判断 x y 是否越界，可能会报错
        while (x >= 0 && y < m) {
            if (matrix[x][y] == target) {
                x--;
                y++;
                count++;
            } else (matrix[x][y] < target) {
                y++;
            } else {
                x--;
            } 
        }
        return count;
    }
}