剑指 Offer 04. 二维数组中的查找（中等数组）

Love The Way You Lie 2022-12-24 10:53 105阅读 0赞

**目录**

题目

思路1

代码

思路2

代码

提升笔记

--------------------

# 题目 #

在一个 n \* m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 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\]  
> \]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

# 思路1 #

暴力，从左上角开始，利用递增，行或列遍历时，超过target就停止。

## 代码 ##

class Solution:
        def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
            n = len(matrix)
            if n == 0:
                return False
            m = len(matrix[0])
            if m == 0:
                return False
            if target < matrix[0][0] or target > matrix[n-1][m-1]:
                return False
            # 缩小到 1 4 7 ；2 5 8 ；3 6 ；10
            for i in range(n):
                if matrix[i][0] > target:
                    return False
                for j in range(m):
                    if matrix[i][j] > target:
                        break
                    if matrix[i][j] == target:
                        return True
            return False

# 思路2 #

利用规律，从左下角或右上角开始找。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 示意图

左下角为例，如果比目标值大，说明右边也大，那么向上找。如果比目标值小，说明目标值在右侧（不一定本行），向上找。如果越界，说明没有。

## 代码 ##

class Solution:
        def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
            n = len(matrix)
            if n == 0:
                return False
            m = len(matrix[0])
            if m == 0:
                return False
            if target < matrix[0][0] or target > matrix[n-1][m-1]:
                return False
            i, j = len(matrix) - 1, 0
            while i >= 0 and j < m:
                if matrix[i][j] > target: 
                    i -= 1
                elif matrix[i][j] < target: 
                    j += 1
                else: 
                    return True
            return False

# 提升笔记 #

*  多利用已知条件
 *  打破刻板印象，尝试换个等方式遍历

更多oj内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

更多python相关内容：[【python总结】python学习框架梳理][python_python]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221120/ca7c45c97f094cd4bcf69282f3cd1ae5.png
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489
[lady_killer9]: https://space.bilibili.com/374432302