搜索二维矩阵II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例

现有矩阵 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，返回 true。
给定 target = 20，返回 false。

思路

思路1 暴力法

直接二维数组遍历

思路2: 按照已有顺序遍历

按照题目给的信息，则可根据原数组的排序方式，设置index从数组第一行最后一列元素开始遍历，这样以m+n的算法复杂度得出结果

代码

思路2：代码

public class Solution &#123;
    public boolean searchMatrix(int[][] matrix, int target) &#123;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) &#123;
            return false;
        &#125;
        int rows = matrix.length;
        int columns = matrix[0].length;
        int rowIndex = 0;
        int colIndex = columns - 1;
        boolean result = false;

        while (rowIndex < rows && colIndex >= 0) &#123;
            while (rowIndex < rows && colIndex >= 0 && matrix[rowIndex][colIndex] > target) &#123;
                colIndex --;
            &#125;
            while (rowIndex < rows && colIndex >= 0 && matrix[rowIndex][colIndex] < target) &#123;
                rowIndex ++;
            &#125;
            if (rowIndex < rows && colIndex >= 0 && target == matrix[rowIndex][colIndex]) &#123;
                result = true;
                break;
            &#125;
        &#125;
        return result;
    &#125;
&#125;