搜索二维矩阵 II

题目链接

搜索二维矩阵 II

题目描述

注意点

• 矩阵具有以下特性：
  每行的元素从左到右升序排列。
  每列的元素从上到下升序排列。

解答思路

• 最初想到使用深度优先遍历+剪枝实现，但是运行后超出时间限制了
• 可以直接遍历整个矩阵查找，虽然不超时但是耗时毕竟高
• 从右上角开始遍历矩阵，也就是x最初为0，y最初为col - 1，从右上角开始毕竟matrix[x][y]与target之间的关系，直到超出边界
  （1）如果相等，说明已搜索到，直接返回true
  （2）如果matrix[x][y]小于target，则应该往下进行搜索，将x + 1
  （3）如果matrix[x][y]大于target，则应该往左进行搜索，将y - 1

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length, col = matrix[0].length;
        int x = 0, y = col - 1;
        while (x < row && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] < target) {
                x++;
            } else {
                y--;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

关键点

• 从右上角开始遍历整个矩阵，想当与Z字形查找