Ac solution code


  • 0

    The key point of Divide&Conquer is discarding efficiently, which is actually the key point of all algorithms.

    In this question, top-right point is the kind of the middle point of the matrix. (if we imagine a line crossing top-left=>top-right=>bottom-right of the matrix. This line is exactly in the ascending order.)

    Say top-right point is matrix[i][j] (i = 0..rows-1; j = 0..columns-1)
    1) if matrix[i][j] == target, return true;
    2) if matrix[i][j] > target, we discard jth column (Because matrix[i][j] is top-right, which means all numbers in jth column >= matrix[i][j]);
    3) if matrix[i][j] < target, we discard ith row (Because matrix[i][j] is top-right, which means all numbers in ith row <= matrix[i][j]).
    

    Time complexity = O(m + n)

    As there's only one pass, and i is 0..n-1, j is 0..m-1, so the complexity is O(m + n).

    JAVA Code:

    public boolean searchMatrix(int[][] matrix, int target) {
    	int rows = matrix.length, cols = matrix[0].length, i = 0, j = cols - 1;
        while (i < rows && j >=0) { 
        	if (matrix[i][j] == target) return true;
        	else if (matrix[i][j] > target) j--;
        	else i++;
        }
        return false;
    }

  • 0
    B

    very clear explaination. Thanks.


Log in to reply
 

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