提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

算法-寻找两个正序数组的中位数

算法数组 两个 寻找 中位数 正序
2023-06-13 09:18:56 时间

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

相关文章