寻找两个正序数组的中位数

Leetcode Link: 4. 寻找两个正序数 组的中位数 - 力扣（LeetCode）

题目

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

算法的时间复杂度应该为 O(log (m+n)) 。

中位数指的是一个数组中间位置的数字，如果中间位置为两个，则为这两个的均值

解法一

思路： 本思路较为简单但是不满足题目的时间要求

可以直接extend之后sort，时间复杂度$O(NlogN)$，空间O$(m+n)$

题解：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        N = len(nums1)+len(nums2)
        if N % 2 == 0:
            mid = [N//2-1, N//2]
        else:
            mid = [N//2]
 
        nums1.extend(nums2)
        nums1.sort()
        # 计算中位数
        res = 0
        for p in mid:
            res += nums1[p]
        return res/len(mid)

解法二

思路：

两个关键：1. nums1 和 nums2 都已经排好序了； 2. 求中位数

因此只要通过遍历，遍历到中间的位置即可，可以避免创建出一个辅助数组

其长度为nums1和nums2的和，来对遍历的两个数组的数字进行保存。

题解：时间$O(n+m)$

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        p = p1 = p2 = 0
        p_val = None
 
        res = 0
        N = len(nums1)+len(nums2)
        if N % 2 == 0:
            ind = set([N//2-1, N//2])
            n = 2
        else:
            ind = set([N//2])
            n = 1
        
        while(len(ind) != 0):
            
            if p1 < len(nums1) and p2 < len(nums2) and nums1[p1] < nums2[p2]:
                p_val = nums1[p1]
                p1 += 1
            elif p1 < len(nums1) and p2 < len(nums2) and nums1[p1] > nums2[p2]:
                p_val = nums2[p2]
                p2 += 1
            elif p1 >= len(nums1):
                p_val = nums2[p2]
                p2 += 1
            else:
                p_val = nums1[p1]
                p1 += 1
 
            if p in ind:
                ind.remove(p)
                res += p_val
        
            p += 1
        return res/n

解法三

思路：看到题目要求的时间复杂度，显然需要使用二分法。

然而本题的二分法也有两种，一种是对中位数的二分，一种是对两个数组 nums1 和 nums2 的二分。

本题解介绍对中位数的二分。

中位数的本质是什么？

本质是一个有序数组中的中间的那一个或者两个数字。 换句话说，是第 K 小的数字，或者第 K 和第 K+1 小的数组的均值。

因此，本题就变成了，求 nums1 和 nums2 中，合起来第 K 小的数字（或者第 K+1）小的数字。

在进入题解之前，我们先声明 index 和位置的关系。 在一个数组中，数组的第 K 个位置，其 index 是 K-1，因为 python 的数组索引是从 0 开始的。请牢牢记住这个关系，并时刻检查我们的某个值的实际意义是 index 还是位置。

回顾题解二，它是再找第 k 小的数字，它是怎么找的？ 一个一个比较，然后每次寻找时丢弃一个数字

我们能不能只看一眼，然后实现一次多丢弃几个数字？ 可以，这就是本题的思路，对第 K 小的数字进行二分。

下面的所有的 K，其意义都是位置

比如说，在两个有序的数组 A 和数组 B 中，我们想找第 K 个最小值

• 假设$x<K$（x 也是位置）

• 我们分别拿出第 x 个数字： A[x-1] 和 B[x-1]，可以确定的是，这两个数字一定分别是 A 和 B 中第 x 小的数字。

• 如果 A[x-1]<B[x-1]，我们可以肯定，在 A 和 B 组成的整体中，第 K 小的数字一定在 A[x:] 和 B 组成的整体中（即我们丢掉了 A[0:x] 上的数字，注意A和B是有序的）。

• 那么此时，我们应该在 A[x:] 和 B 组成的整体中，寻找第 K-x 个最小值。

• 反之亦然，这便是本题的根本思路。

但是 $x$ 取多少合适？

• 若 $x>K//2$，我们最后需要回头找()
• 若 $x<K//2$，我们需要多找
• 因此 $x=K//2$ 最好，即我们对第 K 个最小值的 K 进行二分，并且能够使用递归。

题解：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        # 在有序的数组arr1和arr2中寻找第K个最小值(K不是index，是位置，其index是K-1)
        def get_minK(arr1, arr2, K):
	        # 递归终止条件
            if arr1 == []:
                return arr2[K-1]
            if arr2 == []:
                return arr1[K-1]
            if K == 1:
                return arr1[0] if arr1[0] < arr2[0] else arr2[0]
 
            mid = K // 2 
 
            if mid > len(arr1): # arr1数量不够mid个
                val1 = arr1[-1] # 则取最后一个，扔的话就直接扔arr1
                val2 = arr2[mid-1]
                if val1 > val2:
                    return get_minK(arr1, arr2[mid:], K-mid)
                else:
                    return get_minK([], arr2, K-len(arr1))
            elif mid > len(arr2):
                val1 = arr1[mid-1]
                val2 = arr2[-1]
                if val1 > val2:
                    return get_minK(arr1, [], K-len(arr2))
                else:
                    return get_minK(arr1[mid:], arr2, K-mid)    
            else:
                val1 = arr1[mid-1]
                val2 = arr2[mid-1]
                if val1 > val2:
                    return get_minK(arr1, arr2[mid:], K-mid)
                else:
                    return get_minK(arr1[mid:], arr2, K-mid)
        # 主函数入口
        n1 = len(nums1)
        n2 = len(nums2)
        N = n1 + n2
		# 偶数个需要找俩位置的值取均值
        if N % 2 == 0:
            res1 = get_minK(nums1, nums2, N//2)
            res2 = get_minK(nums1, nums2, N//2+1)
            res = (res1+res2) / 2
        else:
            res = get_minK(nums1, nums2, N//2+1)        
        return res
 

该方法有几个需要注意的点：

1. 递归终止条件中，必需有 K==1，因此若 K=1，则 mid=0，此时会陷入死循环，K-mid=1-0=1=K
2. 时刻牢记 K 是位置，是位置，是位置，然后分析每个索引为什么这样写。

我们发现上面的代码有点冗余，主要原因是我们每次都要比较 arr1 和 arr2 的长度。

我们通过修改代码，保证 arr1 的长度一定小于 arr2 的长度，对代码进行精简

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        # 在有序的数组arr1和arr2中寻找第K个最小值(K不是index，是位置，其index是K-1)
        def get_minK(arr1, arr2, K):
	        # 保证len(arr1) < len(arr2)
            if len(arr1) > len(arr2):
                return get_minK(arr2, arr1, K)
 
            if arr1 == []:
                return arr2[K-1]
            if K == 1:
                return arr2[0] if arr1[0] > arr2[0] else arr1[0]
 
            mid = K // 2 
 
            if mid > len(arr1):
                val1 = arr1[-1]
                val2 = arr2[mid-1]
                if val1 > val2:
                    return get_minK(arr1, arr2[mid:], K-mid)
                else:
                    return get_minK([], arr2, K-len(arr1))
            else:
                val1 = arr1[mid-1]
                val2 = arr2[mid-1]
                if val1 > val2:
                    return get_minK(arr1, arr2[mid:], K-mid)
                else:
                    return get_minK(arr1[mid:], arr2, K-mid)
        
        n1 = len(nums1)
        n2 = len(nums2)
        N = n1 + n2
 
        if N % 2 == 0:
            res1 = get_minK(nums1, nums2, N//2)
            res2 = get_minK(nums1, nums2, N//2+1)
            res = (res1+res2) / 2
        else:
            res = get_minK(nums1, nums2, N//2+1)        
        return res
 

解法四

对 nums1 和 nums2 进行二分 请在review的时候思考，再次进行笔记，留做作业。

启发和联系

如果对时间复杂度有 $log$要求的，通常都需要用到二分查找