4.寻找两个正序数组的中位数 Median of Two Sorted Arrays

妖狐艹你老母 2022-12-29 04:52 128阅读 0赞

## 题目描述 ##

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

**进阶**：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

**示例 1**：

> 输入：nums1 = \[1,3\], nums2 = \[2\]  
> 输出：2.00000  
> 解释：合并数组 = \[1,2,3\] ，中位数 2

**示例 2**：

> 输入：nums1 = \[1,2\], nums2 = \[3,4\]  
> 输出：2.50000  
> 解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5

**示例 3**：

> 输入：nums1 = \[0,0\], nums2 = \[0,0\]  
> 输出：0.00000

**示例 4**：

> 输入：nums1 = \[\], nums2 = \[1\]  
> 输出：1.00000

**示例 5**：

> 输入：nums1 = \[2\], nums2 = \[\]  
> 输出：2.00000

来源：力扣（LeetCode）[链接][Link 1]

## 第一次题解 ##

没有管时间复杂度，直接写的题解。执行用时：40 ms, 在所有 Python3 提交中击败了98.69%的用户；内存消耗：14.9 MB, 在所有Python3 提交中击败了5.17%的用户。

class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            nums1.extend(nums2)
            nums1.sort()
            s = len(nums1)
            if s % 2 == 0:  # 偶数个元素
                return (nums1[s // 2] + nums1[s // 2 - 1]) / 2.0
            else:   # 奇数个元素
                return float(nums1[(s - 1) // 2])

## 最优题解 ##

参考LeetCode上热评第一的老哥写的，他得思路很清晰。执行用时：56 ms, 在所有 Python3 提交中击败了60.86%的用户；内存消耗：15.2 MB, 在所有 Python3 提交中击败了5.17%的用户。

二分查找求解：设两个有序数组的长度分别为m和n，为了简化代码使用一个小trick，分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。加入 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。

class Solution:
        def findMedianSortedArrays(self, nums1: List[int],nums2: List[int]) -> float:
            def findkth(nums1: List[int], nums2: List[int], k: int) -> float:
                m, n = len(nums1), len(nums2)
                # 特殊情况
                if m > n:
                    return findkth(nums2, nums1, k)
                if not nums1:  # nums1为空,直接返回nums2的第k个数
                    return nums2[k - 1]
                if k == 1:  # m和n中各只有一个数，返回最小值
                    return min(nums1[0], nums2[0])
                # 二分查找的一般情况
                midIndex1 = min(k // 2 - 1, m - 1)
                midIndex2 = min(k // 2 - 1, n - 1)
                if nums1[midIndex1] < nums2[midIndex2]:
                    return findkth(nums1[midIndex1 + 1:], nums2, k - midIndex1 - 1)
                else:
                    return findkth(nums1, nums2[midIndex2 + 1:], k - midIndex2 - 1)
    
            m, n = len(nums1), len(nums2)
            left, right = (m + n + 1) // 2, (m + n + 2) // 2
            return (findkth(nums1, nums2, left) + findkth(nums1, nums2, right)) / 2

[Link 1]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays