LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

本文主要是介绍LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给你一个满足下述两条属性的 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
-10⁴ <= matrix[i][j], target <= 10⁴

解题思路一：先二分查找行，再二分查找列。

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)

这篇关于LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---