环球短讯！算法-寻找两个正序数组的中位数

• 2023-04-26 18:19:45 来源：腾讯云

【资料图】

给定两个大小分别为 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

复制

标签：