数组 - LeetCode 04.二维数组中的查找

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数target，判断该数是否在该二维数组中。

[
  [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.

思考：

将矩阵逆时针旋转 45° 发现其类似于二叉搜索树:

• 对于每个元素，其左分支元素更小、右分支元素更大
• 从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target

image.png

“根节点” 对应矩阵 “左下角” 或 “右上角” 元素，称之为 标志数。若以矩阵左下角元素为标志数flag :

• 若 flag > target，则 target 一定在 flag 所在行的上方 ，即 flag 所在行可被消去
• 若 flag < target，则 target 一定在 flag 所在列的右方 ，即 flag 所在列可被消去

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

算法流程：

1. 从矩阵左下角元素（索引设为 (i, j) ）开始遍历，并与target对比：

• 当 matrix[i][j] > target 时，执行 i-- ，即消去第 i 行元素
• 当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素
• 当 matrix[i][j] = target 时，返回 true ，代表找到target

2. 若行索引或列索引越界，则代表矩阵中无目标值，返回 false

每轮 i-- 或 j-- 后，相当于生成了“消去一行（列）的新矩阵”， 索引(i,j) 指向新矩阵的左下角元素（标志数），因此可重复使用以上性质消去行（列）。

image.png

复杂度分析：

• 时间复杂度 O(M+N)：其中，N 和 M 分别为矩阵行数和列数，此算法最多循环M+N次。
• 空间复杂度 O(1): i, j 指针使用常数大小额外空间。