前言

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

若是你和我一样是个算法菜鸡,那么最推荐的是先把剑指offer的问题搞明了,其次再去刷LeetCode等习题,这样对于面试突击异常有用,由于面试官最常考的算法题都在这本书里。

若是你发现看这本书很吃力,可以先直接参考些网上的代码,照着抄一遍,明白下算法题是应该解题,多抄几道问题,你就对算法题的做法有感受了,这个高考做牢固套路数学题是一样的。

对于剑指offer题解这个系列,我的写作思绪是,对于看过文章的读者,能够做到:

  • 迅速领会该题常见解答思绪(奇技淫巧不包括在内,节约人人时间,着实有研究需求的人可以查阅其它资料)
  • 思绪只管贴近原书(例如书中提到的面试官经常会要求不改变原数组,或者有空间限制等,只管体现在代码中,保证读者可以不遗漏书中细节)
  • 只管精简话语,制止冗长注释
  • 给出代码可运行,注释齐全,关注细节问题
  • 代码能够通过牛客网在线编程《剑指offer》测试

《剑指offer题解》系列

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

  • 关注我的民众号:后端手艺漫谈,点击民众号导航栏:剑指offer题解
  • 剑指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

又搜索了他们的下边,

,

以太坊开奖网

www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。

,
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导航页)
  • 各平台博客

关注我

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

主要关注后端开发,数据平安,爬虫,物联网,边缘盘算等偏向,迎接交流。

各大平台都可以找到我

  • 微信民众号:后端手艺漫谈
  • Github:@qqxx6661
  • CSDN:@Rude3Knife
  • 知乎:@Zhendong
  • 简书:@蛮三刀把刀
  • 掘金:@蛮三刀把刀
  • 头条:@后端手艺漫谈

原创博客主要内容

  • Java知识点温习全手册
  • Leetcode算法题剖析
  • 剑指offer算法题剖析
  • SpringBoot菜鸟入门实战系列
  • SpringCloud菜鸟入门实战系列
  • 爬虫相关手艺文章
  • 后端开发相关手艺文章
  • 逸闻趣事/好书分享/小我私家兴趣

小我私家民众号:后端手艺漫谈


民众号:后端手艺漫谈.jpg

若是文章对你有辅助,不妨珍藏,投币,转发,在看起来~