你的位置:首页 > Java教程

[Java教程]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 }