难度: Medium
Submission
运行时间: 83 ms
内存: 16.4 MB
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
# class BinaryMatrix(object):
# def get(self, row: int, col: int) -> int:
# def dimensions(self) -> list[]:
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
m, n = binaryMatrix.dimensions()
res = n
last = n -1
for i in range(m):
start, end = 0, last
while start + 1 < end: # this line
mid =(start + end)//2
if binaryMatrix.get(i, mid) ==1:
end = mid
else:
start = mid
if binaryMatrix.get(i, start) ==1:
res = min(res, start)
last = res
elif binaryMatrix.get(i, end) ==1:
res = min(res, end)
lsat = res
return res if res != n else -1
# TC: O(m log n), where m is the number of rows and n is the number of columns.
# class Solution:
# def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
# m, n = binaryMatrix.dimensions()
# i, j = 0, n-1
# res = -1
# while i < m and j >= 0:
# if binaryMatrix.get(i, j) == 1:
# res = j # Update result since we found a 1
# j -= 1 # Move left
# else:
# i += 1 # Move down
# return res
# TC: O(M+N); SC: O(1)
#The second solution is better. It has a linear time complexity relative
# to the dimensions of the matrix
Explain
题解中使用的是二分搜索来优化查找最左端包含1的列。对于每一行，都从0到上一行找到的最左端一列的索引(last)进行二分搜索。如果在中点找到1，那么尝试寻找是否有更左侧的1；否则继续向右搜索。这种方法利用了矩阵的性质：如果当前行的某列为1，那么所有下面行的同列也为1。因此，每找到一个新的最左端的1，都可以缩小后续行搜索的范围，提高效率。
时间复杂度: O(m log n)
空间复杂度: O(1)
# 定义一个类Solution
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
m, n = binaryMatrix.dimensions() # 获取矩阵的维度，行和列
res = n # 初始化结果为列数，表示还未找到包含1的最左列
last = n - 1 # 设置最初的搜索边界为最右列
for i in range(m): # 遍历每一行
start, end = 0, last # 设置当前行的搜索范围
while start + 1 < end: # 使用二分搜索找到包含1的最左列
mid = (start + end) // 2 # 计算中点
if binaryMatrix.get(i, mid) == 1: # 如果中点是1
end = mid # 更新结束点
else:
start = mid # 更新开始点
if binaryMatrix.get(i, start) == 1: # 检查开始点是否为1
res = min(res, start) # 更新结果
last = res # 更新搜索边界
elif binaryMatrix.get(i, end) == 1: # 检查结束点是否为1
res = min(res, end) # 更新结果
last = res # 更新搜索边界
return res if res != n else -1 # 如果找到了包含1的列，返回其索引，否则返回-1
Explore
在题解中，每一行的搜索开始前将`start`重置为0是为了确保不错过可能存在于当前行更左侧的1。尽管`end`已被上一行的结果调整，但当前行可能在更左侧的列包含1。尽管这样做可能会导致一些重复的搜索，但它确保了算法不会错过任何更左侧的1，这对于找到最左端包含1的列是必要的。
使用`start + 1 < end`作为循环条件是为了防止二分搜索进入死循环，并在循环结束时留下两个潜在的候选列（即`start`和`end`），这两列需要进一步检查以确定哪一列是包含1的最左列。如果使用`start <= end`作为条件，可能在某些情况下，循环不会留下这两个候选列，从而可能错过最左侧的1。该方法不会导致漏检列，而是为了更准确地识别最左侧的1。
在二分搜索结束后，需要分别检查`start`和`end`位置的值，因为二分搜索的退出条件是`start + 1 < end`，这意味着最后`start`和`end`两点是相邻的，因此都有可能是最左端的1。仅检查`end`可能会错过`start`位置如果它更左侧且为1的情况。因此，为了确保找到最左侧的1，需要检查这两个位置。
如果在某一行中`last`已经是0，此时的逻辑依然会执行二分搜索，尽管此时的搜索区间非常小（从0到0）。这确实是一种资源的浪费，因为在这种情况下，没有必要执行二分搜索。为了优化，可以在开始搜索之前添加一个检查，如果`last`为0，则直接返回0，避免不必要的搜索。