4. Median of Two Sorted Arrays

Title

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

Solve

暴力

亏我一开始还想着用归并呢，结果直接合并→排序→判断就能AC，两行代码解决战斗。

def findMedianSortedArrays_violence(self, nums1: List[int], nums2: List[int]) -> float:nums3 = sorted(nums1 + nums2)return nums3[int(len(nums3) / 2)] if len(nums3) % 2 else (nums3[int(len(nums3) / 2)] + nums3[int(len(nums3) / 2 - 1)]) / 2

划分数组

暴力的方法毕竟没有什么技术含量，还是得搞一搞牛掰格拉斯的算法。

在统计中，中位数被用来：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

首先，在任意位置i将A划分成两个部分：

left_A i right_AA[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]

由于A中有m个元素，所以有m+1种划分的方法(i∈[0,m])。

len(left_A)=i len(right_A)=m−i

当i=0时，left_A为空集，当i=m时，right_A为空集。

采用同样的方式，在任意位置j将B划分成两个部分：

left_B j right_BB[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]

将left_A和left_B放入一个集合，将right_A和right_B放入另一个集合，再把这两个新的集合分别命令为left_part和right_part：

left_part | right_partA[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]

---

当A和B的总长度是偶数时，如果可以确定：

len(left_part)=len(right_part)

max(left_part)<=min(right_part)

那么，{A,B}中的所有元素已经被划分成相同长度的两个部分，left_part中的元素总是小于或等于right_part中的元素，中位数就是left_part的最大值和right_part的最小值的平均值：
$$median=\frac{max(left\_part)+min(right\_part)}{2}$$

---

当A和B的总长度是奇数时，如果可以确定：

len(left_part)=len(right_part)+1

max(left_part)<=min(right_part)

那么，{A,B}中的所有元素已经被划分成两个部分，left_part比right_part多一个元素，并且left_part中的元素总是小于或等于right_part中的元素，中位数就是left_part的最大值：
$$median=max(left\_part)$$

---

第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。

第二个条件对于总长度是偶数和奇数的情况是一样的。

要确保这两个条件，只需要保证：

i+j=m−i+n−j（当 m+n 为偶数）或 i + j = m - i + n - j + 1（当 m+n 为奇数）。等号左侧为left_part的元素个数，等号右侧为right_part的元素个数。整理可得：
$$i+j=int(\frac{m+n+1}{2})$$

0<=i<=m,0<=j<=n。规定len(A)<=len(B)，即m<=n，否则交换A和B，这样对于任意的i∈[0,m]，都有$$j=\frac{m+n+1}{2}-i\in [0,n]$$此时我们在[0,m]的范围内枚举i即可通过计算得到j。

B[j-1]<=A[i]以及A[i-1]<=B[j]，即left_part的最大值小于等于right_part的最小值。

为了简化分析，假设A[i−1],B[j−1],A[i],B[j]总是存在，对于 i=0、i=m、j=0、j=n 这样的临界条件，规定 A[−1]=B[−1]=−∞，A[m]=B[n]=∞ 即可。

这也是比较直观的：当一个数组不出现在left_part时，对应的值为负无穷，就不会对求left_part的最大值产生影响，当一个数组不出现在right_part时，对应的值为正无穷，就不会对求right_part的最小值产生影响。

现在我们需要做的是：在[0,m] 中找到 i，使得：
$$B[j-1]\le A[i]$$$$A[i-1]\le B[j]$$$$j=\frac{m+n+1}{2}-i$$

当i从0~m递增时，A[i-1]递增，B[j]递减，所以一定存在一个最大的i满足A[i−1]≤B[j]，如果i是最大的，那么说明i+1不满足。将i+1带入可以得到A[i]>B[j−1]，因此可以证明它等价于：在[0,m] 中找到 i，使得：
$$A[i-1]\le B[j]$$$$j=\frac{m+n+1}{2}-i$$

我们可以对 i 在 [0, m]的区间上进行二分搜索，找到最大的i满足A[i−1]≤B[j]，就得到了划分的方法。

此时，划分left_part元素中的最大值，以及划分right_part元素中的最小值，才可能作为这两个数组中的中位数。

复杂度分析

时间复杂度：O(logmin(m,n)))，其中 m 和 n 分别是数组nums1 和 nums2 的长度。查找的区间是 [0, m]，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为 O(logm)。由于我们可能需要交换 nums1 和 nums2 使得 m≤n，因此时间复杂度是 O(logmin(m,n)))。

空间复杂度：O(1)。

Code

def findMedianSortedArrays_binary(self, nums1: List[int], nums2: List[int]) -> float:if len(nums1) > len(nums2):return self.findMedianSortedArrays_binary(nums2, nums1)m, n = len(nums1), len(nums2)left, right, maxNumber = 0, m, 2 ** 19maxLeft, minRight = 0, 0while left <= right:i = (left + right) // 2j = (m + n + 1) // 2 - inums_i_1 = -maxNumber if i == 0 else nums1[i - 1]nums_i = maxNumber if i == m else nums1[i]nums_j_1 = -maxNumber if j == 0 else nums2[j - 1]nums_j = maxNumber if j == n else nums2[j]if nums_i_1 <= nums_j:left = i + 1maxLeft, minRight = max(nums_i_1, nums_j_1), min(nums_i, nums_j)else:right = i - 1return (maxLeft + minRight) / 2 if (m + n) % 2 == 0 else maxLeft

总结

以上是生活随笔为你收集整理的4. Median of Two Sorted Arrays的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。