剑指Offer [Python]

剑指Offer [Python]

从今天开始攻克 「剑指Offer」。网络上众大神分享的思路及代码，大都已经非常仔细和清楚了。抱着学习的态度，开启「剑指Offer [Python] 」系列博文 —— 「转载」思路详细易懂的、python语言的众大神博文，加之对各方资料进行「整理 & 汇总」，「学习 & 对比」多种思路&# 暴力解法 vs 快速解法）。

八月快来了，秋招要到了，一起加油拿下编程吧！✋

❤️ 「更多题目」

《剑指Offer [Python] | 目录索引》

• 题目

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

一、快速解法

• 思路
  首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

• 举例
  如果在一个二维数组中找到数字7，存在则返回True，如果没找到则返回False。

首先，8大于7，下一次只需要在8的左边区域查找；然后，5小于7，下一次只需要在5的下方区域查找；按照这种规则进行查找，如果查找到相同的，则返回True，否则返回False。

• Python实现：

class Solution:def Find(self, target, array):rows = len(array)cols = len(array[0])if rows > 0 and cols > 0 :row = 0col = cols - 1while ( row < rows and col >= 0) :if target == array[row][col]:return Trueelif target < array[row][col]:col -= 1elif target > array[row][col]:row += 1else:return Falseif __name__=='__main__':target=2array=[[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]solution=Solution()ans=solution.Find(target,array)print(ans)来源：

二、暴力解法

• 思路
  遍历数组中所有元素
• Python实现

class Solution:# array 二维列表def Find(self, target, array):# write code herefor line in array:if target in line:return Truereturn False
--------------------- 
作者：谓之小一 
来源：CSDN 
原文： 
版权声明：本文为博主原创文章，转载请附上博文链接！

三、参考资料