【剑指offer题解】二维数组中的查找

拼搏现实的明天。 2023-06-18 08:00 6阅读 0赞

![format_png][]

# 前言 #

众所周知，对于面试而言，《剑指offer》是一本“好书”。

如果你和我一样是个算法菜鸡，那么最推荐的是先把剑指offer的题目搞明白，其次再去刷LeetCode等习题，这样对于面试突击非常有用，因为面试官最常考的算法题都在这本书里。

如果你发现看这本书很吃力，可以先直接参考些网上的代码，照着抄一遍，理解下算法题是应该解题，多抄几道题目，你就对算法题的做法有感觉了，这个高考做固定套路数学题是一样的。

**对于剑指offer题解这个系列，我的写作思路是，对于看过文章的读者，能够做到：**

*  迅速了解该题常见解答思路（奇技淫巧不包括在内，节省大家时间，实在有研究需求的人可以查阅其它资料）
 *  思路尽量贴近原书（例如书中提到的面试官经常会要求不改变原数组，或者有空间限制等，尽量体现在代码中，保证读者可以不漏掉书中细节）
 *  尽量精简话语，避免冗长解释
 *  给出代码可运行，注释齐全，关注细节问题
 *  代码能够通过[牛客网在线编程][Link 1]《剑指offer》测试

## 《剑指offer题解》系列 ##

你可以通过以下几种途径查看我的《剑指offer题解》系列：

*  关注我的公众号：后端技术漫谈，点击公众号导航栏：剑指offer题解
 *  [剑指offer题解专栏(CSDN)][offer_CSDN]
 *  各大博客平台我的账号（见本文最下方）

# 题目介绍 #

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

# 解题思路 #

## 方法一 ##

首先能够想到的肯定是一行一行或者一列一列遍历，判断数组中是否含有该整数。该方法显然是最笨拙的二维数组遍历，面试官也不会满意，时间复杂度是O(n^2)

### 代码 ###

#### Python ####

class Solution:
        def Find(self, target, array):
            for i in range(len(array)):
                for j in range(len(array[0])):
                    if array[i][j]==target:
                        return True
            return False

## 方法二 ##

我们思考下，既然大的数字都在靠右边/下边，能否能利用行列的数据变化规律来优化下解法，如果寻找的目标数大于现在的数字，那么目标数字是在当前位置的右边或下边，如果所寻找的目标数小于现在的数字，那么目标数字在当前位置的左边或上边。举个例子，如下图数组所示：

1  2  3   4
    2  3  8   9
    3  4  9   10
    4  5  10  11

我们的位置是1，要找8，8大于1，那么在1的右边和下边区域进行下一步的搜索。

如果我们先搜索他的右边，

2  3   4
    3  8   9
    4  9   10
    5  10  11

又搜索了他们的下边，

2  3  8   9
    3  4  9   10
    4  5  10  11

这时候我们发现

3  8  9
    4  9  10
    5  10 11

这个区域搜索了两次，我们是从数组的第一个数\[0\]\[0\]取的，遇到了重复搜索区域的问题。有没有方法去除重复的搜索区域呢，我们发现，当从右上角取第一个数的时候，可以去除重复的搜索区域，还是以这个数组为例，取4，搜索8，发现8比4大，那么8不可能出现在4这一行，只需要从下边搜索即可。如果寻找3，3比4小，4那一列后续的数都大于4，只需要从左边搜索即可。

1  2  3   4
    2  3  8   9
    3  4  9   10
    4  5  10  11

我们还可以发现左下角的点也可以去除重复搜索区域，总结起来的话，有点像变量控制法的感觉，将一个变量控制住，根据另外一个变量的规律，得出结论。

这样我们将时间复杂度降为了O(n)

### 代码 ###

#### Java ####

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

#### Python ####

class Solution:
        def Find(self, target, array):
            if array == ([] or [[]]):
                return False
            row = len(array)
            col = len(array[0])
            i=0
            j=col-1
            while 0<=i<row and 0<=j<col:
                if target>array[i][j]:
                    i=i+1
                elif target<array[i][j]:
                    j=j-1
                else:
                    return True
            return False

# 总结 #

题目简单，小伙伴们需要理解的是算法题应该注重的是效率优化，暴力穷举能够解决问题，但说服不了面试官。

# 我的《剑指offer题解》系列 #

你可以通过以下两种途径查看《剑指offer题解》系列：

*  关注我的公众号：**后端技术漫谈**，点击公众号下方：剑指offer题解
 *  [剑指offer题解专栏(CSDN导航页)][offer_CSDN]
 *  各平台博客

# 关注我 #

我是一名后端开发工程师。

主要关注后端开发，数据安全，爬虫，物联网，边缘计算等方向，欢迎交流。

### 各大平台都可以找到我 ###

*  **微信公众号：后端技术漫谈**
 *  Github：[@qqxx6661][qqxx6661]
 *  CSDN：[@Rude3Knife][Rude3Knife]
 *  知乎：[@Zhendong][Zhendong]
 *  简书：[@蛮三刀把刀][Link 2]
 *  掘金：[@蛮三刀把刀][Link 3]
 *  头条：[@后端技术漫谈][Link 4]

### 原创博客主要内容 ###

*  Java知识点复习全手册
 *  Leetcode算法题解析
 *  剑指offer算法题解析
 *  SpringBoot菜鸟入门实战系列
 *  SpringCloud菜鸟入门实战系列
 *  爬虫相关技术文章
 *  后端开发相关技术文章
 *  逸闻趣事/好书分享/个人兴趣

### 个人公众号：后端技术漫谈 ###

![公众号：后端技术漫谈.jpg][.jpg]

**如果文章对你有帮助，不妨收藏，投币，转发，在看起来~**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8xMi8xLzE2ZWMwMzYzOTQ1MjA5NmE?x-oss-process=image/format,png
[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[offer_CSDN]: https://blog.csdn.net/qqxx6661/column/info/37267
[qqxx6661]: https://github.com/qqxx6661
[Rude3Knife]: http://blog.csdn.net/qqxx6661
[Zhendong]: https://www.zhihu.com/people/yang-zhen-dong-1/
[Link 2]: https://www.jianshu.com/u/b5f225ca2376
[Link 3]: https://juejin.im/user/5b48015ce51d45191462ba55
[Link 4]: https://www.toutiao.com/c/user/85058181995/#mid=1648450372537357
[.jpg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS8xMS8yNy8xNmVhY2M4NjM3Njg1ZjQx?x-oss-process=image/format,png