条码在线系统
388 2023-04-03 05:22:34
最近做了几道题,发现有一点相似之处,解法却又不相似,我整理成一起看看有什么化学反应。
剑指offer04 二维数组中的查找
给定一个二维数组,行和列都是递增函数,然后给定一个整数,问该数组里面是否有该整数
[[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
这道题如果是按照传统的顺序来遍历的话,可以一列一列去遍历,然后每一列都二分,但是这样不够高效。
学到的一个方法就是从其他角度去遍历该数组:从右上角去开始遍历。
从右上角开始,那么对于每一个点,都有:左边比它小,下边比它大。
因此,可以根据该性质去遍历数组:如果要找的数比当前元素小,就往左边找,如果比它大,就往下面找。这样的寻找是有方向的,可以在O(m+n)的时间内完成。
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool: # O(m+n) if len(matrix) == 0 or len(matrix[0]) == 0: return False n = len(matrix) m = len(matrix[0]) i = 0 j = m - 1 while matrix[i][j] != target: if matrix[i][j] < target: i += 1 else: j -= 1 if j < 0 or i > n - 1: return False return True
对于矩阵 [[ ]] 和 [ ],要特判它们不是写成
len(matrix[0]) is None
或者 len(matrix) is None
而应该是0。。。