题解 | #二维数组中的查找#
二维数组中的查找
http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
2021.8.19
# 2021.8.19 # -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code here self.target = target self.array = array row = len(array) #求列表行数 colume = len(array[0]) #求列表列数 for i in range(row): for j in range(colume): if i<row and j<colume: #防止索引超过范围 k = colume - j - 1 agent = array[i][k] #列表访问方法 if target == agent: return True elif target < agent: j += 1 elif target > agent: i += 1 else: continue return False #测试 array = [ [1,2,8,9], [2,4,9,12] ] target = 6 #实例化 find = Solution() #find继承了Solution这个类的所有属性 print(find.Find(target,array)) #调用继承来的类里面的Find函数，并且传入参数
思路
类似于二分查找，根据题目，如果拿数组中任意一个元素与目标数值进行比较，如果该元素小于目标数值，那么目标数值一定是在该元素的下方或右方，如果大于目标数值，那么目标数值一定在该元素的上方或者左方。 对于二分查找来说，每次比较只能移动一个指针，在二维数组的查找中，两个指针是一个上下方向移动，一个是左右方向移动。两个指针可以从同一个角出发。 假设我们从左上角出发，也就是row=0 和 col=0，如果元素小于目标数值，我们会将row往下移或着col往右移，这样，被屏蔽的区域可能会是目标元素所在的区域。比如row+=1，那么第一行除左上角以外的元素就被忽略了，如果col+=1，那么第一列出左上角以外的元素就被忽略了。因此这样是不可行的。所以本题从右上角出发寻找解题思路。
个人总结：：因为需要向两个方向进行查询，如果从左上角开始的话，如果target大于该出的索引，则算法下一步不知道该往哪走了。索引得从右上角（或者左下角）开始，如果大于则是一个方向，如果小于则是另一个方向。
OPPO公司福利 1091人发布
