难度: Medium
Submission
运行时间: 38 ms
内存: 37.1 MB
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
def bisect_search(nums, val):
m = len(nums)
l = 0
r = m - 1
while l <= r:
mid = (r+l) // 2 # 0 1 2 => 1; 0 1 2 3 => 1
cur_val = nums[mid]
if cur_val == val:
return val # 找到了
elif cur_val < val:
l = mid + 1
elif cur_val > val:
r = mid - 1
# 没有找到
return nums[l] if l < m else None
match = 1
val = mat[0][0]
cur_row = 0
while match <= len(mat):
cur_row += 1
ret = bisect_search(mat[cur_row % len(mat)], val)
if ret == val:
match += 1
elif ret is None:
return -1
elif ret != val:
match = 1
val = ret
return val
Explain
此题解采用的思路是遍历矩阵的每一行，使用二分搜索方法在当前行中查找上一行的最小元素。如果在当前行找到了该元素，继续到下一行查找；如果没有找到，或找到的元素不是该元素，则将当前行的最小元素设为新的目标，从当前行重新开始匹配。这个过程重复直到遍历完所有行。如果某个元素在所有行中都被找到，则返回该元素；如果遇到某行中不存在任何元素或找不到目标元素，则返回-1。
时间复杂度: O(n log m)
空间复杂度: O(1)
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
def bisect_search(nums, val):
m = len(nums)
l = 0
r = m - 1
while l <= r:
mid = (r+l) // 2
cur_val = nums[mid]
if cur_val == val:
return val # 找到了目标值
elif cur_val < val:
l = mid + 1
elif cur_val > val:
r = mid - 1
return nums[l] if l < m else None # 返回较大的邻近值或None
match = 1
val = mat[0][0]
cur_row = 0
while match <= len(mat):
cur_row += 1
ret = bisect_search(mat[cur_row % len(mat)], val)
if ret == val:
match += 1 # 找到目标值，继续下一行
elif ret is None:
return -1 # 当前行中没有元素或找不到更大的元素
elif ret != val:
match = 1 # 重新开始匹配
val = ret
return val # 找到了所有行的公共元素
Explore
在算法中，每当当前行的搜索结果不是目标值时，意味着目标值不是所有行的共有元素。因此，算法会选择当前行的一个新的较大邻近值作为新的目标值，并重新开始搜索，希望找到一个存在于所有行中的新的共有元素。此时重置匹配计数器match为1是因为我们开始针对一个新的值重新匹配所有行。如果直接结束算法，那么可能错过找到存在于所有行的其他公共元素的机会。
选择返回较大的邻近值而非直接失败或返回-1是为了继续寻找可能存在的共有元素。如果直接返回失败或-1，算法会失去继续查找其他可能的共有元素的机会。返回较大的邻近值后，算法可以用这个新值作为新的搜索目标，探索是否有一个更大的值作为所有行的共有元素。这种方法增加了算法的灵活性和可能成功找到共有元素的机会。
确实，代码中有一个逻辑上的遗漏。在给定的代码中，应该有一个检查机制来确保目标值在每一行都被确认过才能返回该值。正确的实现应该包括一个检查步骤，确认match计数器的值是否等于行数，以确保目标值在所有行都被找到。没有这个检查，算法可能会在没有完全验证的情况下提前结束，这可能导致错误的返回结果。
这是算法设计中的一个潜在缺陷。理论上，每当算法找到一个新的目标值时，确实应该检查这个新目标值是否存在于之前的所有行中，以确保它真正是一个共有元素。不进行这样的检查可能导致算法错误地接受一个不是所有行共有的元素。在实际应用中，这种检查是必要的，以提高算法的准确性和可靠性。