0001-0100 - 0004-寻找两个正序数组的中位数 - 《LeetCode》

题目链接
题目描述
示例
- 示例1：
提示
思路
题解
- 思路3：二分查找
- 思路4：二分优化
复杂度分析
- 思路3：二分查找
- 思路3：二分优化

题目链接

题目描述

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

示例

示例1：

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

提示

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10 <= nums1[i], nums2[i] <= 10

思路

思路1：暴力解法
合并数组后排序，直接找中位数。

思路2：双指针
由于两个数组的长度已知，那么中位数的位置也就能得出。维护两个指针，分别指向两个数组的开头，每次移动指向较小数的指针，直到找到中位数。

思路3：二分查找
求中位数实际上就是求第 k 小的数的特殊情况，此时的 k = (m + n) / 2 or k = (m + n) / 2 + 1 ，这里的 m, n 是数组 nums1 和 nums2 的长度。
要找到第 k 小的数，我们首先可以比较 nums1[k/2 - 1] 和 nums2[k/2 - 1] （因为数组是从0开始计数，所以要减一），有以下几种情况：
nums1[k/2 - 1] <= nums2[k/2 - 1] ，此时比 nums1[k/2 - 1] 小的最多有 nums1 的前 k/2 - 1个数和 nums2 的前k/2 - 1数，即最多有 k - 2 个数，因此 nums[k/2 - 1] 不是第 k 小的数。这样可以排除 nums1[0] 到 nums1[k/2 - 1] 的数，此问题就变为求第 k - k/2 小的数。
nums1[k/2 - 1] > nums2[k/2 - 1] 同理，排除 nums2[0] 到 nums2[k/2 - 1] 的数
如果 k/2 - 1 越界，那么我们选取最后一个元素，设原指针为 p1 新指针为 newP1 则此问题就变为求第 newP1 - p1 + 1 小的数。

循环结束的条件：

p1 == m 直接返回 nums2 的第 k 小的元素。
p2 == n 直接返回 nums1 的第 k 小的元素。
k == 1，返回 nums1 和 nums2 中最小的元素。

思路4：分治+二分查找
回想一下中位数的意义：将数组划分为左右两部分，左边的最大值小于右边的最小值。
由此，对于本题，试想，我们将两个数组合并（合并后总大小为 m + n），存在一个中位数，将合并后的数组分成两部分 leftPart 和 rightPart ，其中，数组 nums1 位于 leftPart 的个数为 i 个，数组 nums2 位于 leftPart 的个数为 j 个。
若m + n 为偶数， leftPart 的大小 leftTotal = (m + n) / 2 ；
若m + n 为奇数， leftPart 的大小 leftTotal = (m + n) / 2 + 1 ，即此时中位数为 leftPart 的最大值。

根据整除的性质，上述两种情况可以合并为 leftTotal = (m + n + 1) / 2 ，且有 leftTotal = i + j ，即 j 可由 i 唯一确定。
所以，接下来我们的工作就是找到合适的 i ，使得 nums1[i - 1] <= nums2[j]，且 nums2[j - 1] <= nums1[i] 。
进一步简化，我们证明只要 nums1[i - 1] <= nums2[j] 成立，则就能推出 nums2[j - 1] <= nums1[i] ：

i 递增，j 递减，则存在一个最大的 i 使得 nums1[i - 1] <= nums2[j] 成立，且 i + 1 不满足。那么便有 nums1[i] > nums2[j - 1] 。

所以，经过简化后，我们的工作就是找到最大的 i ，使得 nums1[i - 1] <= nums2[j]：
这个问题又可以转化成，求数 nums2[j] 在数组 nums1 中的插入位置这种经典二分问题。

题解

思路3：二分查找

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            p1 = 0
            p2 = 0
            while True:
                if p1 == m:
                    return nums2[p2 + k - 1]
                if p2 == n:
                    return nums1[p1 + k - 1]
                if k == 1:
                    return min(nums1[p1], nums2[p2])
                newP1 = min(p1 + k // 2 - 1, m - 1)
                newP2 = min(p2 + k // 2 - 1, n - 1)
                if nums1[newP1] <= nums2[newP2]:
                    k -= newP1 - p1 + 1
                    p1 = newP1 + 1
                else:
                    k -= newP2 - p2 + 1
                    p2 = newP2 + 1
        m = len(nums1)
        n = len(nums2)
        if (m + n) % 2 == 1:
            return getKthElement((m + n + 1) // 2)
        else:
            return (getKthElement((m + n) // 2) + getKthElement((m + n) // 2 + 1)) / 2

思路4：二分优化

import sys
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        leftTotal = (m + n + 1) // 2
        left, right = 0, m

        while left < right:
            i = (left + right) // 2
            j = leftTotal - i
            if (nums1[i] < nums2[j - 1]):
                left = i + 1
            else:
                right = i

        i = left
        j = leftTotal - i
        # 考虑极端情况
        nums1LeftMax = (-sys.maxsize if i == 0 else nums1[i - 1])
        nums1RightMin = (sys.maxsize if i == m else nums1[i])
        nums2LeftMax = (-sys.maxsize if j == 0 else nums2[j - 1])
        nums2RightMin = (sys.maxsize if j == n else nums2[j])

        if (m + n) % 2 == 1:
            return max(nums1LeftMax, nums2LeftMax)
        else:
            return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2