Lintcode: Search a 2D matrix II

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

很巧妙的思路，可以从左下或者右上开始找

 1 public class Solution {
 2     /**
 3      * @param matrix: A list of lists of integers
 4      * @param: A number you want to search in the matrix
 5      * @return: An integer indicate the occurrence of target in the given matrix
 6      */
 7     public int searchMatrix(int[][] matrix, int target) {
 8         // write your code here
 9         if (matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
10         int m = matrix.length;
11         int n = matrix[0].length;
12         int count = 0;
13         int row = m-1;
14         int col = 0;
15         while (row>=0 && row<m && col>=0 && col<n) {
16             int cur = matrix[row][col];
17             if (cur == target) {
18                 count++;
19                 col++;
20                 row--;
21             }
22             else if (cur > target) {
23                 row--;
24             }
25             else col++;
26         }
27         return count;
28     }
29 }

这道题的一个优化是对于一个矩阵的最后一行做二分搜索后，删掉前几列和最后一行，得到一个子矩阵。重复这样的操作，时间复杂度是O(min(m,n)log(max(m,n)))。之后跟她提了一下这个方法在m和n相差比较大的时候可能比较有用。

2, 20, 35, 41, 70,

11, 24, 44, 60, 78,

21, 30, 50, 75, 90,

31, 38, 99, 100, 102