LeetCode-074-搜索二维矩阵

搜索二维矩阵

题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/search-a-2d-matrix/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：二分查找法

由于matrix数组的行和列都是有序的，所以采用二分查找法是比较高效的方法，具体查找的过程如下：

首先，从matrix数组的左下角开始查找，即初始索引位i为matrix.length - 1，j为0；

如果当前位置的值等于target，则直接返回true；

如果当前位置的值小于target，则位置右移，即j加一；

如果当前未知的值大于target，则位置上移，即i减一；

查找结束的条件是i不小于0且j不大于matrix[0].length - 1，即查找的值不能超过matrix数组的界限。

如果查找结束都没有找到和target相等的值，则返回false。

public class LeetCode_074 {

    public static boolean searchMatrix(int[][] matrix, int target) {

        // 从matrix数组的左下角开始查找

        int i = matrix.length - 1, j = 0;

        while (i >= 0 && j <= matrix[0].length - 1) {

            if (matrix[i][j] == target) {

                // 如果当前位置的值等于target，直接返回true

                return true;

            } else if (matrix[i][j] < target) {

                // 如果当前位置的值小于target，右移

                j++;

            } else if (matrix[i][j] > target) {

                // 如果当前未知的值大于target，上移

                i--;

            }

        }

        // 如果查找结束都没有找到和target相等的值，则返回false

        return false;

    }

    public static void main(String[] args) {

        int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};

        System.out.println(searchMatrix(matrix, 13));

    }

}

【每日寄语】 生活中有好的日子和不好的日子，不好的日子就咬着牙撑过去，好的日子就会来的，相信明天会更好！

巴特西

LeetCode-074-搜索二维矩阵

搜索二维矩阵

解法一：二分查找法

最新文章

热门文章