[leetcode] 74. Search a 2D Matrix @ python
程序员文章站
2022-07-14 17:53:39
...
原题
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
解法1
先确定target所在的行, 即它<=该行最右边的数. 找到行之后进行二分查找.
Time: O(m + log(n))
Space: O(1)
代码
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# base case
if not matrix: return False
row, col = len(matrix), len(matrix[0])
# edge case
if row == 0 or col == 0:
return False
r, c = 0, col-1
for i in range(row):
if target <= matrix[i][c]:
# binary search
l, r = 0, col-1
while l <= r:
mid = (l+r)//2
if matrix[i][mid] == target:
return True
if target < matrix[i][mid]:
r = mid-1
else:
l = mid+1
return False
else:
continue
return False
解法2
逐行查找
Time: O(m*n)
Space: O(1)
代码
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# base case
if not matrix: return False
for row in matrix:
if target in row:
return True
return False
推荐阅读
-
LeetCode 74. Search a 2D Matrix
-
74. Search a 2D Matrix
-
74. Search a 2D Matrix
-
LeetCode 74. Search a 2D Matrix
-
[leetcode]74. Search a 2D Matrix
-
leetcode -- 74. Search a 2D Matrix
-
LeetCode 74. Search a 2D Matrix
-
[leetcode] 74. Search a 2D Matrix @ python
-
[leetcode]74. Search a 2D Matrix
-
74. Search a 2D Matrix