Lintcode: Search a 2D matrix IIWrite 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 }