What's wrong with my divide and conquer solution?


  • 0
    G
    public class Solution {
        public static boolean searchMatrix(int[][] matrix, int target) {
    		if(matrix==null)return false;
    		int row = matrix.length;
    		int col = matrix[0].length;
    		return partSearch(matrix, 0, 0, row-1, col-1, target);
        }
    	
    	private static boolean partSearch(int[][] matrix,int a,int b,int c,int d,int target){
    		boolean result = false;
    		int i=c,j=d;
    		int temp = matrix[i][j];
    		if(target>temp)return false;
    		for(;i>=a&&j>=b&&temp>target;i--,j--){
    			System.out.println("i--"+i+"---j---"+j);
    		}
    		if(temp==target)result = true;
    		else if(i<a&&j<b)result = false;
    		else if(i<a&&j>=b)result=partSearch(matrix,a,b,c,j,target);
    		else if(i>=a&&j<b)result=partSearch(matrix, a, b, i, d, target);
    		else result=partSearch(matrix, a, j+1, i, d, target)||partSearch(matrix, i+1, b, c, j, target);
    		return result;
    	}
    }
    

    It turns out that my solution is out of time limit.

    I start from bottom right to up left,and if this item is bigger than target,then move to up left.

    Then divide into two little part and recurse again.

    So,what's wrong with my solution?


Log in to reply
 

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