leetcode问题要求在2D矩阵中搜索目标值。两种方法都使用二分搜索。
我的方法:
将矩阵视为长度为rows x columns的单个数组，然后用整数除法和模数在二分查找中得到row和column的索引。它的时间复杂度是O(log [rows x colums])
# Binary search on rows and then on columns
# Time : O(log nm) # binary search on total numbers of cells
# Space : O(1) # same number of pointers (left, right, mid) regardless of size of matrix
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS = len(matrix)
COLUMNS = len(matrix[0])
left = 0
right = ROWS * COLUMNS - 1
# run regular binary search as if dealing with just an array
while left <= right: # <= handles case when left, right are the same and value not considered before
mid = left + ( (right - left) // 2 )
row = mid // COLUMNS
col = mid % COLUMNS # has to be COLUMNS and not ROWS.
# Try [[1,1]] with ROWS, will get index-out-of-range error
# print(f"left = {left} right = {right} mid = {mid} row = {row} col = {col}")
if target < matrix[row][col]:
right = mid - 1
elif target > matrix[row][col]:
left = mid + 1
else:
return True
# not found
return False
Neetcode的方法:
然后我碰到了neetcode的解决方案视频，他消除了rows，然后只关注可能包含目标的row。由于先删除行，然后再搜索可能行的列，所以时间复杂度为O( log[rows] + O[columns] )。
# Binary search on rows and then on columns
# Time : O(log n + log m) # binary search on rows then on columns
# Space : O(1) # same number of pointers (top, bottom, row, left, right) regardless of size of matrix
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS = len(matrix)
COLUMNS = len(matrix[0])
top = 0
bottom = ROWS - 1
while top <= bottom:
row = top + ((bottom-top)//2)
if target < matrix[row][0]:
bottom = row - 1
elif target > matrix[row][-1]:
top = row + 1
else:
# break so you can retain row value and check within the row
break
# ambiguous here: could have ended here because
# of the break in the while loop or the while
# condition failed so check
if top > bottom:
return False
# check within the row. 2nd binary search
left = 0
right = COLUMNS - 1
while left <= right:
# avoid overflow in other languages
mid = left + ((right - left) // 2)
if target < matrix[row][mid]:
right = mid - 1
elif target > matrix[row][mid]:
left = mid + 1
else:
return True
return False
在试图找出大0符号中最优的符号时，我突然想到它们可能是相同的，因为数学中的log(xy) = log(x) + log(y)。它们本质上是一样的吗?
这两个时间复杂度是相等的。
是一个对数恒等式log(x*y) == log(x) + log(y)
所以这两种方法有相同的大o