240/74. Search a 2D Matrix II

Link

Solution

想法:

先確定哪一row，ie 比較 每列的最後一個元素，如果 A[row][colLen-1] > target，那表示target很可能在這裡row中。就開始從colLen-1 -> 0去減少col值去確認哪一個col。

要注意許多edge case. 比方說 空array，或是有row但col是0。

另外本row沒找到，col值可以保留給下一row繼續使用。但要注意col值是否已經小於0

     public boolean searchMatrix(int[][] matrix, int target) {
        int rowLen = matrix.length;
        if(rowLen == 0) return false;
        int colLen = matrix[0].length;
        if(colLen == 0) return false;
        int col = colLen - 1;
        for(int row = 0; row < rowLen; row++){
            if(matrix[row][col] >= target){
                while(col >= 0){
                    if(matrix[row][col] == target) return true;
                    else if(matrix[row][col] < target) break;
                    col--;
                }
                if(col < 0) col = 0;
            }
        }
        return false;
    }

T: O(n+m)