python-leetcode 63.搜索二维矩阵

题目：
给一个满足两条属性的m*n的整数矩阵：
每行中的整数从左到右按非严格递增次序排列
每行的第一个整数大于前一行的最后一个整数
给一个整数target,如果target在矩阵中，返回true,否则返回false

---

方法一：两次二分查找
由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。
对矩阵的第一列元素二分查找，找到最后一个不大于目的值的元素，然后在该元素所在行中二分查找目的是否存在

1. class Solution(object):
2.     def searchMatrix(self, matrix, target):
3.         """
4.         :type matrix: List[List[int]]
5.         :type target: int
6.         :rtype: bool
7.         """
8.         row=bisect.bisect_right([row[0] for row in matrix],target)#用列表推导式获取所有行的第一个元素组成列表,返回的是第一个大于target的行首元素的位置
9.         if row==0: #如果row为0，表示所有行的第一个元素都大于target，矩阵中不可能存在该值
10.             return False
11.         target_row=matrix[row-1]#获取可能包含target的行（row-1位置的这一行）
12.         pos=bisect.bisect_left(target_row,target)#在目标行中使用bisect_left进行二分查找，找到target应该插入的位置
13.         return pos<len(target_row)and target_row[pos]==target#检查找到的位置是否有效且该位置的元素确实等于target

复制代码

时间复杂度：O(logm+logn)=O(logmn),其中mn分别是矩阵的行数和列数
空间复杂度：O（1）

---

方法二：一次二分查找
若将矩阵每一行拼接在上一行的末了，则会得到一个升序数组，我们可以在该数组上二分找到目的元素。

1. class Solution(object):
2.     def searchMatrix(self, matrix, target):
3.         """
4.         :type matrix: List[List[int]]
5.         :type target: int
6.         :rtype: bool
7.         """
8.         m, n = len(matrix), len(matrix[0])
9.         left, right = -1, m * n
10.         while left + 1 < right:
11.             mid = (left + right) // 2
12.             x = matrix[mid // n][mid % n]  #获取行列坐标
13.             if x == target:
14.                 return True
15.             if x < target:
16.                 left = mid
17.             else:
18.                 right = mid
19.         return False
21.         

复制代码

时间复杂度：O(logm+logn)=O(logmn),其中mn分别是矩阵的行数和列数
空间复杂度：O（1）
源自力扣官方题解和灵茶山艾府
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。