难度: Medium
Submission
运行时间: 49 ms
内存: 44.9 MB
from typing import List
class Solution:
def matrixMedian(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
total = m * n
left, right = 1, 10**6
while left < right:
mid = (left + right) // 2
count = 0
for row in grid:
count += bisect_right(row, mid)
if count >= total // 2 + 1:
right = mid
else:
left = mid + 1
return left
from typing import List
import bisect
class Solution:
def matrixMedian(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
total = m * n
left, right = 1, 10**6
while left < right:
mid = (left + right) // 2
count = 0
for row in grid:
count += bisect.bisect_right(row, mid)
if count >= total // 2 + 1:
right = mid
else:
left = mid + 1
return left
Explain
该题解采用了二分查找的思路来寻找矩阵的中位数。首先，初始化左右指针left和right分别为1和10^6（假设矩阵中的元素值在这个范围内）。然后进行二分查找，每次计算中间值mid，并统计矩阵中小于等于mid的元素个数count。如果count大于等于矩阵元素总数的一半加一（total // 2 + 1），则说明中位数应该在左半部分，更新右指针right为mid；否则，说明中位数在右半部分，更新左指针left为mid + 1。当左右指针相遇时，left即为矩阵的中位数。
时间复杂度: O(m * log(n) * log(10^6))
空间复杂度: O(1)
from typing import List
import bisect
class Solution:
def matrixMedian(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0]) # 获取矩阵的行数和列数
total = m * n # 计算矩阵中元素的总数
left, right = 1, 10**6 # 初始化二分查找的左右指针
while left < right:
mid = (left + right) // 2 # 计算中间值
count = 0
for row in grid:
count += bisect.bisect_right(row, mid) # 统计小于等于mid的元素个数
if count >= total // 2 + 1:
right = mid # 更新右指针
else:
left = mid + 1 # 更新左指针
return left # 返回中位数
Explore
在题解中选择1和10^6作为二分查找的左右边界是基于问题描述中的假设或者对数据范围的一般了解。这种设置不意味着矩阵中元素的值必须严格在这个范围内，但它确实假设了矩阵内的元素值大致在这个范围。若实际应用中矩阵元素的范围已知，应该调整这两个边界以匹配实际情况，从而提高算法的效率和准确性。
如果矩阵的行并非完全排序，那么使用二分查找结合`bisect_right`来统计小于等于mid的元素个数的方法将不再适用。这是因为`bisect_right`函数假设行是排序的，以便能够快速确定小于等于mid的元素的个数。若行未排序，则必须先对各行进行排序，或者使用其他算法来寻找中位数。
`bisect_right`函数返回的是插入点的位置，即数组中小于或等于给定值的元素的数量，这正是计算中位数时需要的信息。而`bisect_left`返回的是数组中小于给定值的元素的数量，这在需要统计严格小于某个值的元素数量时使用。在寻找中位数的问题中，我们需要包括等于中间值mid的所有情况，因此使用`bisect_right`更为合适。
在二分查找的过程中，我们通过不断调整left和right的值，缩小查找范围，直至left和right相遇。由于二分查找条件是判断小于等于mid的元素数量是否超过总数的一半，因此最终的left值即为满足条件的最小可能值。实际上，可能存在多个相同的元素值都可以是中位数，尤其是在元素值分布不均或有重复时。算法确保找到的是这些可能值中的最小值，这是符合中位数定义的一种合理解释。