How about this java AC answer?


  • 0
    A
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix == null || matrix.length == 0)
                return false;
                
            return searchMatrixHelper(matrix, 0, matrix[0].length-1, 0, matrix.length-1, target);
        }
        
        public boolean searchMatrixHelper(int[][] matrix, int xs, int xl, int ys, int yl, int target){
            if(xs > xl || ys > yl) 
                return false;
                
            int xSmall = xs;
            while(xs <= xl){
                int m = (xs + xl)/2;
                if(matrix[ys][m] == target)
                    return true;
                else if(matrix[ys][m] > target)
                    xl = m - 1;
                else
                    xs = m + 1;
            }
            
            int ySmall = ys;
            while(ys <= yl){
                int m = (ys + yl)/2;
                if(matrix[m][xSmall] == target)
                    return true;
                else if(matrix[m][xSmall] > target)
                    yl = m - 1;
                else 
                    ys = m + 1;
            }
            
            return searchMatrixHelper(matrix,  xSmall+1, xl, ySmall+1, yl, target);
        }
    }

  • 0
    A

    Just a little explanation. For example,

    [
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]
    

    and the target is 5.

    1st call to helper would be on the whole matrix itself;
    During 1st call, it would find the biggest number on the first column that is smaller than target, which is 3. Then it would find the biggest number on the first row that is smaller than target, which is 7.

    2nd call to helper would be on a subset of the matrix that cuts off 1st and last two rows, as well as 1st and last two columns, i.e.

    [
      [ 5 ],
      [ 6 ],  
    ]
    

    During the 2nd call, the target is found.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.