240 Search a 2D Matrix II

Leetcode

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

从右上角往左下角遍历，如果当前的数大于 target，则往左移动，因为所有小于当前数的数字都在左边，同理如果当前数小于 target 则往下移动。移出去了说明没有找到。

时间复杂度 o(n) ，空间复杂度 o(1)

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