Two java solutons. O(log(m+n)) is better than O(log(m) + log(n))


  • 0
    D

    The best solution must be binary search. So at first I use two bi-searchs to find row_id and col _id. The time complexity is O(log(m) + log(n)). While if we take the matrix as a sorted array, one bi-search is enough. And the tiem complexity is O(log(m+n)).
    The two solutions are below:

    public boolean searchMatrix(int[][] matrix, int target) {
            int col_id = 0;
            int rlen = matrix.length;
            int clen = matrix[0].length;
            int row_id = row_search(matrix, target, 0, rlen-1, clen);
            //System.out.println(row_id);
            if (matrix[row_id][clen-1] < target){
            	row_id += 1;
            }
            //System.out.println(row_id);
            if (row_id >= matrix.length)
            	return false;
            
            col_id = col_search(matrix, target, 0, clen-1, row_id);
            //System.out.println(col_id);
            if(matrix[row_id][col_id] != target)
            	return false;
    		return true;
        }
    	
    public int row_search(int[][] matrix, int target, int begin, int end, int clen){
    		if(begin >= end)
    			return begin;
    		int mid = (begin + end) / 2;
    		if (matrix[mid][clen-1] == target)
    			return mid;
    		else if(matrix[mid][clen-1] < target){
    			return row_search(matrix, target, mid + 1, end, clen);
    		}
    		else
    			return row_search(matrix, target, begin, mid - 1, clen);
    	}
    	
    public int col_search(int[][] matrix, int target, int begin, int end, int row_id){
    		if(begin >= end)
    			return begin;
    		int mid = (begin + end) / 2;
    		if (matrix[row_id][mid] == target)
    			return mid;
    		else if(matrix[row_id][mid] < target){
    			return col_search(matrix, target, mid + 1, end, row_id);
    		}
    		else
    			return col_search(matrix, target, begin, mid - 1, row_id);
    	}
    
    //this is the second solution.
    public boolean searchMatrix2(int[][] matrix, int target){
    		if(matrix.length == 0)
    			return false;
    		int start = 0;
    		int row = matrix.length, col = matrix[0].length;
    		int end = row * col - 1;
    		while(start <= end){
    			int mid = (start + end) / 2;
    			if(matrix[mid/col][mid%col] == target){
    				return true;
    			}
    			else if(matrix[mid/col][mid%col] < target){
    				start = mid + 1;
    			}
    			else{
    				end = mid - 1;
    			}
    		}
    		return false;
    	}

  • 3
    B

    Why is the second solution O(log(m+n))? It's like doing binary search on a sorted array of length mn so the time complexity is O(log(mn)) = O(log(m) + log(n)).


Log in to reply
 

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