BM18　二维数组中的查找¶

中等通过率 26.39%python3核心代码模式样例通过牛客 AC数组

牛客原题　源码

讲解章节：二分

一句话

行列都递增的矩阵，从右上角走阶梯判断 target 是否存在。

解题思路¶

这题考什么¶

选一个「比较结果能排除一整片」的起点，把二维查找降成一条 O(n+m) 的路径。

矩阵行内递增、列内递增，但整体不是有序序列：题面样例第一行结尾是 9，第二行开头是 2，拍平后并不单调，所以不能当成一维数组直接二分。

四个角提供的信息量并不相同：

左上角  右边更大、下边也更大   ->  比它大时两个方向都可能，排除不掉任何区域
右下角  左边更小、上边也更小   ->  比它小时同样无从取舍
右上角  左边更小、下边更大     ->  两个方向单调相反，可用
左下角  上边更小、右边更大     ->  同理可用

取右上角 (r, c) = (0, m-1) 当指针，每次比较只有三种结果：

array[r][c] == target   ->  找到
array[r][c] >  target   ->  第 c 列从 r 往下只会更大，整列排除，c 减一
array[r][c] <  target   ->  第 r 行从 c 往左只会更小，整行排除，r 加一

循环不变量：target 若存在，必落在「第 r 行及以下、第 c 列及以左」的矩形里。每一步让这个矩形少一行或少一列，指针只往左和往下走，绝不回头。

数据规模与复杂度¶

n, m <= 500，值域 |val| <= 1e9，时限其他语言 2 秒。阶梯查找每步砍掉一行或一列，最多走 n + m = 1000 步，时间 O(n+m)、空间 O(1)，正是题面进阶要求的两项。逐格扫描是 O(nm) = 25 万，本题规模下也能过；但把它换成「每行二分」的 O(n log m) 或本文的 O(n+m)，才是这道题想考的东西。

坑在哪¶

起点只能取右上角或左下角。取左上角看似自然，实际比较结果排除不掉任何区域，写出来只能退化成全表扫描。
空矩阵与空行两种退化输入都要挡：题面允许 n、m 取 0。array 为 [] 时直接取 array[0] 会 IndexError；array 为 [[]] 时列数为 0。两个条件缺一不可。
比较结果与移动方向不能配错。array[r][c] > target 时若误写成 r 加一，被丢掉的那一行里可能正藏着 target，结果是漏判返回 False。
双向单调是前提。若题目只保证行内递增而列之间没有关系，阶梯走法立刻失效，那时只能逐行二分，复杂度 O(n log m)。

样例复核¶

target = 7，矩阵 [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]。

(0,3)=9  > 7  ->  c=2
(0,2)=8  > 7  ->  c=1
(0,1)=2  < 7  ->  r=1
(1,1)=4  < 7  ->  r=2
(2,1)=7 命中，返回 True，与样例一致。

参考实现¶

solutions/nowcoder/BM18/sol.py
from typing import List, Optional


class Solution:
    def Find(self, target: int, array: List[List[int]]) -> bool:
        # 两个条件缺一不可：array 为 [] 时 array[0] 会 IndexError，[[]] 时列数为 0
        if not array or not array[0]:
            return False
        n, m = len(array), len(array[0])
        # 右上角「向左变小、向下变大」，两个方向单调相反，比较结果才能排除整行整列
        r, c = 0, m - 1                 # 起点：第 0 行最右一列
        # 循环不变量：target 若存在，必在第 r 行及以下、第 c 列及以左的矩形内
        while r < n and c >= 0:
            v = array[r][c]
            if v == target:
                return True
            if v > target:
                c -= 1                  # 整列都比 target 大，砍掉这一列
            else:
                r += 1                  # 整行都比 target 小，砍掉这一行
        return False                    # 指针走出矩阵：排除掉的区域里都不含 target

BM18 二维数组中的查找¶