题目描述
给定两个大小为 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
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
解法1
解法1使用Binary Search。考虑两个排序数组nums1与nums2，合并后后形成有序数组nums。记|nums1| = n1, |nums2| = n2, |nums| = n, 有n = n1 + n2。对nums求中位数，那么需要取nums的第k个数（n是奇数）或与第k+1个数取平均（n是偶数），其中k = (n + 1) / 2。
nums的这前k个数可能来自于nums1一部分和nums2一部分，我们用m1表示数字来自于nums1的个数，m2表示数字来自于nums2的个数，那么有 m1 + m2 = k。
现在的问题是如何确定m1？我们绘制一张图片来分析中位数的来源。A[i]表示数组nums1的元素；B[i]表示nums2的元素；C[i]表示nums的元素。
前面说过，nums的前k个数分别来自于nums1的前m1个与nums2前m2个，那么C[k-1] = max{A[m1-1], B[m2-1]}, C[k] = min{A[m1], B[m2]}（这样nums1与nums2合并才能使得nums有序）。又因为C[k-1] <= C[k]，所以max{A[m1-1], B[m2-1]} <= min{A[m1], B[m2]}。为了满足这个条件，就要求A[m1-1]<=B[m2]且B[m2-1] <= A[m1]。也就是说，我们寻找m1使得“A[m1-1]<=B[m2]且B[m2-1] <= A[m1]”成立就可以了。
为了寻找满足条件的m1，我们可以对数组nums1进行二分查找。如果A[m1-1] > B[m2]说明m1取的太大了；如果B[m2-1] > A[m1]说明m1取得太小了。
现在有一个边界问题需要考虑，如果m1 == 0，说明nums数组的前k个数不会来自于nums1，我们就取nums2[m2-1]作为C[k-1]；如果m1 == |nums1|，说明我们要取nums1所有元素作为nums的前k个数，那么只能取nums2[m2]作为C[k]。同理，对于m2 == 0与m2 == |nums2|做相同的处理即可。
时间复杂度O(log(min(|nums1|, |nums2|))，空间复杂度O(1)。全部代码如下。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 我们总对短的数组进行binary search
if (nums2.length < nums1.length)
return findMedianSortedArrays(nums2, nums1);
int n = nums1.length + nums2.length;
int k = (n + 1) / 2;
int l = 0, r = nums1.length;
while (l <= r) {
// 0<= m1 <= |nums1|
int m1 = (l + r) >>> 1;
int m2 = k - m1;
if (m1 != 0 && m2 != nums2.length && nums1[m1 - 1] > nums2[m2])
r = m1 - 1;
else if (m2 != 0 && m1 != nums1.length && nums2[m2 - 1] > nums1[m1])
l = m1 + 1;
else {
// 进入此分支说明m1，m2越界，或者正好找到了一个m1，m2使得A[m1-1]<=B[m2]且B[m2-1] <= A[m1]成立
int leftMax, rightMin;
if (m1 == 0) {
leftMax = nums2[m2 - 1];
} else if (m2 == 0) {
leftMax = nums1[m1 - 1];
} else {
leftMax = Math.max(nums1[m1 - 1], nums2[m2 - 1]);
}
if (n % 2 == 1)
return leftMax;
if (m1 == nums1.length)
rightMin = nums2[m2];
else if (m2 == nums2.length)
rightMin = nums1[m1];
else {
rightMin = Math.min(nums1[m1], nums2[m2]);
}
return (leftMax + rightMin) / 2.0;
}
}
return 0;
}
}
参考：