LeetCode-74-搜索二维矩阵

题目

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

题解

这一题在于确定target进行二分查找所在的行，找到了那行，直接二分查找就行。

怎么确定行呢？

遍历matrix，当前为i行，如果target比i行的第一个数字大，比第i行最后一个数字小，那么就在该i行进行查找；

如果target < matrix[0][0] || target > matrix[matrix.length - 1][matrix[0].length - 1]说明target不在矩阵里，返回false即可。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 同一行里的元素，直接用二分查找；问题在于定位到行
        // i行，如果比第i行第一个大，比第i行最后一个数字小，在当前行找
        if (target < matrix[0][0] || target > matrix[matrix.length - 1][matrix[0].length - 1]) {
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            if (target >= matrix[i][0] && target <= matrix[i][matrix[0].length - 1]) {
                return search(matrix[i], target);
            }
        }
        return false;
    }

    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) {
                return true;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}