接下来是两道二维数组查找的题目,看一下二维数组中二分查找的特点,或者说应用。
74. Search a 2D Matrix 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.
Input:
matrix = [
[1,3,5,7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
题目解析:
该题二维数组的特点是,按顺序拼接为一维数组后,也仍然是有序的,因此思路也很简单,先按每行第一个元素二分查找,确定目标元素在哪一行;再在该行进行二分查找。代码如下,做了许多边界条件处理,性能不错,代码有许多优化空间,不过了解思路即可。
由于前面所说,该二维数组拼为一维,也仍然是有序,所以可以把2D数组当成一维的,通过 // 和 %计算行和列,只进行一次二分查找即可。
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if not m:
return False
n = len(matrix[0])
if not n:
return Falsest = matrix[0][0]
ed = matrix[-1][-1]
if st > target or ed < target:
return Falselt, rt = 0, m-1
pos = lt
while lt <= rt:
mid = (lt + rt) // 2
# print(mid)
num_st = matrix[mid][0]
if num_st <= target and (mid == m-1 or target < matrix[mid+1][0]):
pos = mid
break
elif num_st > target:
rt = mid - 1
else:
lt = mid + 1
# print(pos)
lt, rt = 0, n-1
if matrix[pos][0] > target or matrix[pos][-1] < target:
return False
while lt <= rt:
mid = (lt + rt) // 2
# print(mid)
num = matrix[pos][mid]
if num == target:
return True
elif num > target:
rt = mid - 1
else:
lt = mid + 1
return False
240. Search a 2D Matrix II 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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Consider the following matrix:
[
[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]
]
Given target =
5
, return true
.Given target =
20
, return false
.题目解析:
此题的2D数组就是真二维了,自上而下自左到右都有序。鄙人介绍提供如下两种解题方法:
一, 仿照上题思路,通过每行第一个和最后一个元素,确定target可能会在的某几行(因此用了两个while循环);然后在这几行中分别进行二分查找(for循环中一个while循环),整体上时间复杂度是2*O(logm)+mlog(n),但是实际上性能还不错。
二,是一个值得思考和学习的方法,从后面的Discus部分学习来的,时间复杂度O(m+n),从第一行最后一个元素开始查找,大于target光标左移,小于target光标下移,自己看代码思考一下吧~
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if not m:
return False
n = len(matrix[0])
if not n:
return False
if matrix[0][0] > target or matrix[-1][-1] < target:
return Falselt, rt = 0, m-1
while lt <= rt:
mid = (lt + rt) // 2
m_num = matrix[mid][0]
if m_num <= target and (mid == m-1 or matrix[mid+1][0] > target):
break
elif m_num > target:
rt = mid - 1
else:
lt = mid + 1
pos_l = midlt, rt = 0, m-1
while lt <= rt:
mid = (lt + rt) // 2
m_num = matrix[mid][-1]
if m_num < target and (mid == m-1 or matrix[mid+1][-1] >= target):
break
elif mid == 0 and m_num >= target:
mid = -1
break
elif m_num >= target:
rt = mid - 1
else:
lt = mid + 1pos_r = mid + 1
for i in range(pos_r, pos_l+1):
row = matrix[i]
lt, rt = 0, n-1
while lt <= rt:
mid = (lt + rt) // 2
num = row[mid]
if num == target:
return True
elif num > target:
rt = mid - 1
else:
lt = mid + 1
return False
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
def search(mat, row, col, target):
if col < 0 or row == len(mat):
return False
num = mat[row][col]
if num == target:
return True
elif num > target:
return search(mat, row, col-1, target)
else:
return search(mat, row+1, col, target)if not len(matrix) or not len(matrix[0]):
return Falsereturn search(matrix, 0, len(matrix[0])-1, target)
至此,二分查找的问题学习的差不多了~套路及常见问题基本如此。
下一章节将是最重要的树。
推荐阅读
- Python 3的教程
- Python常用标准库(pickle序列化和JSON序列化)
- Python实战|逻辑回归实战-股票客户流失预警模型(Python代码)
- Python <算法思想集结;之初窥基础算法
- LeetCode|从斐波那契数入手动态规划
- python|Python数据分析与处理——北京高考分数线统计分析
- python|妙不可言,Python 可视化竟可以这么玩啊
- python|真香啊,手把手教你使用 Python 获取基金信息
- python|图文并茂,Python轻松生成PDF数据分析报告