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.ExampleConsider the following matrix:[    [1, 3, 5, 7],    [2, 4, 7, 8],    [3, 5, 9, 10]]Given target = 3, return 2.ChallengeO(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 }