算法-寻找两个正序数组的中位数_环球热点
发布时间：2023-04-26 18:14:55
来源：腾讯云
(资料图片仅供参考)
给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
这道题要求找出两个已排序数组的中位数，且算法的时间复杂度应为 O(log(m+n))。其中，O 表示时间复杂度的上限，log 表示对数，m 和 n 分别表示两个数组的大小。
我们可以使用二分查找算法来解决这个问题。首先，我们将两个数组分别记为 nums1 和 nums2。为了方便，我们假设 nums1 的长度小于等于 nums2 的长度。
我们可以在 nums1 中选取一个位置 i，在 nums2 中选取一个位置 j，使得 i+j=(m+n+1)/2，其中 m 和 n 分别是两个数组的长度。如果我们能够保证：
nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]
那么，我们就已经将 nums1 和 nums2 分成了两个部分，且第一部分中的所有元素都小于第二部分中的所有元素。此时，中位数即为：
当 m+n 为奇数时，中位数为 max(nums1[i-1],nums2[j-1])； 当 m+n 为偶数时，中位数为 (max(nums1[i-1],nums2[j-1])+min(nums1[i],nums2[j]))/2。
为了保证上述条件成立，我们可以使用二分查找算法在 [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标签：
