My AC Solution, divide and conquer. Feel this solution is better than O(m+n), T(n) = lgn + 2T(n/2)


  • 1

    Use binary search we find the break point and discard upper left and bottom right area.

    public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length==0 || matrix[0][0]>target) return false;
            return helper(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
        }
    public boolean helper(int[][] matrix, int target, int xstart, int xend, int ystart, int yend) {
            if(xstart>xend || ystart>yend) return false;
        	int xs = xstart, xe = xend, ys = ystart, ye = yend;
        	while(xs<xe || ys<ye) {
        		int xm = xs + (xe-xs)/2, ym = ys + (ye-ys)/2;
        		if(matrix[xm][ym]==target) return true;
        		else if(matrix[xm][ym]<target) {
        			xs = (xs==xe? xs: xm+1);
        			ys = (ys==ye? ys: ym+1);
        		} else {
        			xe = xm;
        			ye = ym;
        		}
        	}
            if(matrix[xs][ys]==target) return true;
        	return helper(matrix, target, xs, xend, ystart, ys-1) || 
        	       helper(matrix, target, xstart, xs-1, ys, yend);
        }

Log in to reply
 

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