为了保证上述条件成立,我们可以使用二分查找算法在 [0, m] 中查找合适的 i 值。在每次二分查找时,我们可以计算出 j 的值,然后检查上述条件是否成立。如果成立,则返回中位数;否则,我们就需要调整 i 的值,以便满足上述条件。具体地,如果 nums1[i-1] > nums2[j-1],则我们需要将 i 的值减小,否则将 i 的值增大。时间复杂度为 O(log(min(m,n)))。
下面是代码实现:
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) left, right = 0, m while left <= right: i = (left + right) // 2 j = (m + n + 1) // 2 - i if i < m and nums2[j-1] > nums1[i]: left = i + 1 elif i > 0 and nums1[i-1] > nums2[j]: right = i - 1 else: if i == 0: max_left = nums2[j-1] elif j == 0: max_left = nums1[i-1] else: max_left = max(nums1[i-1], nums2[j-1]) if (m + n) % 2 == 1: return max_left if i == m: min_right = nums2[j] elif j == n: min_right = nums1[i] else: min_right = min(nums1[i], nums2[j]) return (max_left + min_right) / 2