LeetCode - 4. 寻找两个正序数组的中位数

. - 力扣（LeetCode）

题目

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• 

解题方案

首先明确中位数的位置

1. 暴力解法（合并数组）

合并成一个新数组，然后sort，取中位数。

• 边界情况：合并后数组的长度为0，则无中位数
• 合并数组(nums)长度为偶数(n)，则中位数为第位和第位的平均值，即
• 合并数组(nums)长度为奇数(n)， 则中位数为第位，即

接下来，人生苦短，我用Python~

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# 合并数组并排序nums1.extend(nums2)nums1.sort()length = len(nums1)if length < 1:return Noneif length % 2 == 0:return (nums1[length // 2 - 1] + nums1[length // 2]) / 2else:return nums1[length // 2]

分析时空复杂度

• 记nums1长度为m, nums2长度为n
• 合并数组时间复杂度是，空间复杂度是
• 数组排序时间复杂度是，空间复杂度是

故总的时间复杂度是，空间复杂度是

虽然看上去代码非常精炼，但是从时空复杂度上看，算法并不好，毕竟题目中"正序（从小到大）数组"这个条件没有用到。因此考虑有序归并

2. 暴力解法优化版（有序合并数组）

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:m = len(nums1)n = len(nums2)# 合并数组nums = []if m == 0:nums = nums2elif n == 0:nums = nums1else:index_1 = 0index_2 = 0while True:if index_1 >= m and index_2 >= n:breakelif index_2 >= n or (index_1 < m and nums1[index_1] <= nums2[index_2]):nums.append(nums1[index_1])index_1 += 1elif index_1 >=m or (index_2 < n and nums1[index_1] > nums2[index_2]):nums.append(nums2[index_2])index_2 += 1total_length = len(nums)if total_length < 1:return Noneelif total_length % 2 == 0:return (nums[total_length // 2 - 1] + nums[total_length // 2]) / 2else:return nums[total_length // 2]

分析时空复杂度

• 时间复杂度为合并数组花费的时间，
• 空间复杂度为合并后数组的空间， （如果不存储合并的数组，空间复杂度可以做到O(1)）

题目给出的条件都用上了，时空复杂度也得到了提升，但仍然不符合题目要求的 O(log (m+n))的时间复杂度，需要进一步优化。

有序数组寻找中位数，考虑二分法。

3. 二分法

考虑一个长度为n有序数组的中位数，其中位数：

• 如果n为奇数，则中位数为第大的数。
• 如果n为偶数，则中位数为第大的数和第大的数的平均值。

因此，中位数问题可以转换为另一个问题，寻找数组中第k小的数

（对于长度为偶数的情况，需要寻找两次，并取平均值）

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""寻找两个正序整数数组中，第k小的数"""passdef findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""中位数计算入口函数"""total_length = len(num1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(num1, nums2, total_length // 2 + 1)

接着看如何寻找两个正序数组中第k小的数：

• 如果时间复杂度是O(log (m+n))，考虑用二分法。

先看下面这个例子：

 

由此，我们可以总结我们两个正序数组中，寻找第k小的数的思路：

1. 如果k=1, 则首先比较两个数组首位元素，取最小的一个。

2. 如果k>1, 则比较两个数组中第个元素，较小的一个数组中的第1~个元素一定是小于我们目标值的，因此可以排除这一段（如上图中灰色部分），在剩余元素中继续寻找第()小的元素。

3. 如果某个数组完全被排除掉了，则直接在剩余的另一个数组中定位目标元素即可。如下面的例子：

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""寻找两个正序整数数组中，第k大的数"""# 记录数组长度m = len(nums1)n = len(nums2)# 记录数组可以查找的起始位置索引index_1 = 0index_2 = 0while True:# 极端情况1 - nums1已经被排除为空if index_1 >= m:return nums2[index_2 + k - 1]# 极端情况2 - nums2已经被排除为空if index_2 >= n:return nums1[index_1 + k - 1]# 极端情况3 - 寻找最小的数if k == 1:return min(nums1[index_1], nums2[index_2])# 正常情况, 二分查找new_index_1 = min(k // 2 - 1 + index_1, m - 1)new_index_2 = min(k // 2 - 1 + index_2, n - 1)if nums1[new_index_1] <= nums2[new_index_2]:k -= (new_index_1 - index_1 + 1)index_1 = new_index_1 + 1else:k -= (new_index_2 - index_2 + 1)index_2 = new_index_2 + 1def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""寻找中位数 入口函数"""total_length = len(nums1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(nums1, nums2, total_length // 2 + 1)

分析时空复杂度

• 时间复杂度

• 空间复杂度 

AI会怎么做？

智谱清言给出了一种更高效的解法，划分数组二分法。

思路：

• 对一个长度为n的数组，从任意位置i将数组划分为两部分，可以有n+1种分发（），如图所示，4个元素的数组，有4+1=5种划分方法。

• 中位数的作用是什么呢？将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
  • 对数组A从i位置进行划分，对数组B在j位置划分，数组A的左半部分和数组B的左半部分合起来叫做left_part, 数组A的有半部分和数组B的右半部分合起来叫做right_part， 则中位数是这样的一种划分：
    • 对于两个数组长度之和为偶数的情况：，中位数为,此时划分位置满足
    • 对于两个数组长度之和为奇数的情况：，中位数为，此时划分位置满足
    • 合并上述两种，可以知道中位数情况下的划分：
    • 如果我们保证(避免j计算出负数)， 可以导出：
    • 通过上述推导，中位数问题可以转换为：寻找，使得：且，其中，
    • 进一步简化为：在中寻找最大的，使得,其中。接下来就可以在上对进行二分查找了。

如此复杂的推导过程，又是担心被AI取代的一天。。。

def findMedianSortedArrays(nums1, nums2):# 确保 nums1 是较短的数组if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums1[i] < nums2[j - 1]:# i 需要增大imin = i + 1elif i > 0 and nums1[i - 1] > nums2[j]:# i 需要减小imax = i - 1else:# 找到合适的 i 和 jmax_of_left = 0if i == 0: max_of_left = nums2[j - 1]elif j == 0: max_of_left = nums1[i - 1]else: max_of_left = max(nums1[i - 1], nums2[j - 1])if (m + n) % 2 == 1:return max_of_leftmin_of_right = 0if i == m: min_of_right = nums2[j]elif j == n: min_of_right = nums1[i]else: min_of_right = min(nums1[i], nums2[j])return (max_of_left + min_of_right) / 2.0# 示例
print(findMedianSortedArrays([1, 3], [2]))  # 输出: 2.0
print(findMedianSortedArrays([1, 2], [3, 4]))  # 输出: 2.5