Leetcode 04
Published:
寻找两个正序数组的中位数
寻找两个正序数组的中位数 [hard]
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
Example
1.
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
2.
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
思路
left_part | right_part
A[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 的总长度是偶数时，如果：
1. len(left_part)=len(right_part)
2. max(left_part)≤min(right_part)
那么，{A,B}中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值：
median= max(left_part)+min(right_part)/2
当 A 和 B 的总长度是奇数时，如果：
1. len(left_part)=len(right_part)+1
2. max(left_part)≤min(right_part)
那么，{A,B} 中的所有元素已经被划分为两个部分，前一部分比后一部分多一个元素，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值：
median=max(left_part)
所以只要满足：
1. i+j= (m+n+1)/2
2. B[j−1]≤A[i] 以及 A[i−1]≤B[j]，即前一部分的最大值小于等于后一部分的最小值。
对于第二点，其实就是：
在[0,m] 中找到最大的 i，使得：
A[i−1]≤B[j]
证明：
1. 当 i从 0∼m 递增时，A[i−1] 递增，B[j]递减，所以一定存在一个最大的 i 满足A[i−1]≤B[j];
2. 如果 i是最大的，那么说明 i+1不满足。将i+1 带入可以得到 A[i]>B[j−1]，也就是 B[j−1]<A[i]，就和我们进行等价变换前 i 的性质一致了（甚至还要更强）。
为了简化分析，假设 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]=∞ 即可。这也是比较直观的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。
因此我们可以对 i 在[0,m] 的区间上进行二分搜索
时间复杂度：O(logmin(m,n)))
空间复杂度：O(1)
Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m, ansi = -1;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
while (left <= right) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
if (nums_im1 <= nums_j) {
ansi = i;
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
left = i + 1;
}
else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
}