leetCode-240:Search a 2D Matrix II

问题描述

给定一个整数二维数组表示矩阵，矩阵中每一行从左到右都是递增的，每一列从上到下都是递增的。要求判断给定的数字是否在矩阵中。题目链接：**点我**

样例输入输出

输入：[[1,4,5],[2,6,7]]， 8

输出：false

输入：[[1,4,5],[2,6,7]]， 4

输出：true

问题解法

此题最简单粗暴的做法就是直接遍历矩阵，但是这样并没有利用上矩阵的特点：每一行从左到右都是递增的，每一列从上到下都是递增的。所以这样的效率也是最低的。优化一点，可以从上到下每一行进行二分查找，这样也仅是利用了矩阵每一行的数字是递增这一特性，并没有利用每一列数字是递增这一特点，所以这也不是最高效的查找方式。高效的查找方式是：从矩阵的右上角进行查找，如果当前数字比目标数字小，则向下一行进行查找（利用矩阵列数字递增这一特点），如果当前数字比目标数字大，则向左进行查找（利用矩阵行数字递增这一特点），如果查找范围超过矩阵边界，说明目标数字不在矩阵中。代码如下

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