LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】
- 题目描述：
- 解题思路一：先二分查找行，再二分查找列。
- 解题思路二：暴力遍历，也能过。
- 解题思路三：用python的in。
题目描述：
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
解题思路一：先二分查找行，再二分查找列。
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m, n = len(matrix), len(matrix[0])up, down = 0, m - 1while up <= down:mid = up + (down - up) // 2if matrix[mid][0] < target:up = mid + 1elif matrix[mid][0] > target:down = mid - 1else:return Trueprint(matrix[up-1], target)left, right = 0, n - 1while left <= right:mid = left + (right - left) // 2if matrix[up-1][mid] < target:left = mid + 1elif matrix[up-1][mid] > target:right = mid - 1else:return Truereturn False# 同意
class Solution(object):def searchMatrix(self, matrix, target):M, N = len(matrix), len(matrix[0])col0 = [row[0] for row in matrix]target_row = bisect.bisect_right(col0, target) - 1if target_row < 0:return Falsetarget_col = bisect.bisect_left(matrix[target_row], target)if target_col >= N:return Falseif matrix[target_row][target_col] == target:return Truereturn False
时间复杂度：O(logn + logm)
空间复杂度：O(1)
解题思路二：暴力遍历，也能过。
class Solution(object):def searchMatrix(self, matrix, target):M, N = len(matrix), len(matrix[0])for i in range(M):for j in range(N):if matrix[i][j] == target:return Truereturn False
时间复杂度：O(nm)
空间复杂度：O(1)
解题思路三：用python的in。
class Solution(object):def searchMatrix(self, matrix, target):M, N = len(matrix), len(matrix[0])for i in range(M):if target > matrix[i][N - 1]:continueif target in matrix[i]:return Truereturn False
时间复杂度：O(logn + m)
空间复杂度：O(1)
