时间戳

首页 > 解决方案 > 计算两个排序列表中位数的相反分区

python - 计算两个排序列表中位数的相反分区

问题描述

来自：https ://leetcode.com/problems/median-of-two-sorted-arrays/description/

有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。

找到两个排序数组的中位数。总体运行时间复杂度应为 O(log (m+n))。

示例 1：

nums1 = [1, 3]
nums2 = [2]

中位数为 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

中位数为 (2 + 3)/2 = 2.5

我有以下解决方案（基于此 YouTube 视频：https ://www.youtube.com/watch?v=LPFhl65R7ww ）：

class Solution:
    def findMedianSortedArrays(self, x, y):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        x, y = (x, y) if len(x) <= len(y) else (y, x)
        total_len_even = (len(x) + len(y)) % 2 == 0
        left, right = 0, len(x)
        while left <= right:
            partition_x = (left + right) // 2
            # not sure why we add 1 below...
            half_el_count = (len(x) + len(y) + 1) // 2
            partition_y = half_el_count - partition_x 

            max_left_x = float('-inf') if partition_x == 0 else x[partition_x - 1]
            min_right_x = float('inf') if partition_x == len(x) else x[partition_x]

            max_left_y = float('-inf') if partition_y == 0 else y[partition_y - 1]
            min_right_y = float('inf') if partition_y == len(y) else y[partition_y]

            if max_left_x <= min_right_y and max_left_y <= min_right_x:
                return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2.0 if total_len_even else float(max(max_left_x, max_left_y))
            elif max_left_x > min_right_y:
                right = partition_x - 1
            else:
                left = partition_x + 1

其中partition_x和partition_y表示此分区索引之前的所有元素都小于或等于整体中位数。

我的问题围绕着这一行： half_el_count = (len(x) + len(y) + 1) // 2 想法是我们想要找到分区 y，这样，如果你取组合列表中的元素总数，分区 x 之前的元素数 + 分区 y 之前的元素数是一半元素的总数（毕竟我们是在试图找到中位数）。

但是，half_el_count 不应该是：(len(x) + len(y)) // 2？在视频中，他提到添加 1 可以更轻松地处理偶数或奇数情况，但我不确定这意味着什么。

Leetcode 解决方案也只是说： i+j=m−i+n−j (or: m - i + n - j + 1m−i+n−j+1)没有说明为什么要添加额外的 1。有人可以解释为什么我们添加额外的 1 吗？

标签： pythonalgorithm

解决方案

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        a=nums1+nums2
        a.sort()
        n=len(a)
        if len(a)==0 or len(a)==1:
            return a[0]
        if n%2!=0:
            s=(n/2)
            return a[s]
        else:
            return (a[n/2]+a[(n/2)-1])/2.0

我在您提供的 leetcode 链接上对此进行了测试，没有任何运行时错误。希望这可以帮助

推荐阅读