leetcode

LeetCode 240. Search a 2D Matrix II

Problem

LeetCode 240. Search a 2D Matrix II

1. 题目简述

给出一个m * n大小的矩阵，以及一个target，返回该矩阵中是否存在该数字。该矩阵有如下两条性质：

  1. 每一行从左到右都是递增的整形数
  2. 每一列从上至下都是递增的整形数

例如：

Consider the following 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]
]
Given target = 5, return true.

Given target = 20, return false.

2. 算法思路

相关问题：

  1. LeetCode 74. Search a 2D Matrix
  2. LeetCode 378. Kth Smallest Element in a Sorted Matrix

这是一类很特殊的二分查找的题目，建议背下来，它并不是全局有序，而是拥有一些有序的特性，总结为下面两点：

  1. 矩阵的左上角的值全局最小；右下角的值全局最大；
  2. 对于每个L型的路径，其都是有序的，例如第一列和最后一行构成的L型或者第一行和最后一列构成的L型。

那么利用这些性质，我们应该如何去做呢？根据二分查找，我们将start设置为matrix[0][0]，end设为matrix[m - 1][n - 1]（m、n为行数和列数）。然后我们遍历的起点要从右上角或者左下角开始，每次舍弃一行或者一列。

二分搜索

注意一下这里的起点和终点即可。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //这个的规律在于，第一行与最后一列连在一起是有序的，从右上角出发，如果这个数比target大，那么它就不可能在第一行，如果这个数比target小，那么它就不可能在最后一列。
        int m = matrix.length, n = 0;
        if (m != 0) {
            n = matrix[0].length;
        }
        if (m == 0 || n == 0 || target < matrix[0][0] || target > matrix[m - 1][n - 1]) {
            return false;
        }

        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (target < matrix[i][j]) {
                j--;
            } else if (target > matrix[i][j]) {
                i++;
            } else {
                return true;
            }
        }

        return false;
    }
}