There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解题思路
时间复杂度： O(log(min(m + n)))
题眼：
1、两个数组时已排序的
2、解法的时间复杂度在O（log(m+n)）以内。(下面的思路优于这个复杂度）
从题意知，在考察二分查找。
中位数
我们的目的是找到这样一个数。能将一个数集划分成等长的两个子集，使得其中一个子集的数全部小于另一个子集。
思路：.
- 定义小的子集为
left_part，大的子集为right_part。我们要做的是将接收到的两个数组nums1和nums2，一部分较小的数分到left_part，剩余较大的数分到right_part。且需要保证两个子集等长（这时不包括中位数本身）。nums1用i划分成，nums2用j划分，如下：
nums1[0], ..., nums1[i -1] | nums1[i], ..., nums1[m]
nums2[0], ..., nums2[j -1] | nums2[j], ..., nums2[n]
满足以上描述的划分的数学表达：
// 1. 左边个数 = 右边个数
i + j = (m - i) + (n - j); // 中位数不在数组中的情况，即 (m + n) % 2 = 0 时。
i + j = (m - i) + (n - j) + 1; // 中位数本身存在两个数组中，即 (m + n) % 2 != 0 时。
// 我们约定把中位数划分到 left_part 。
// 2. left_part 全部小于或等于 right_part , 因为 nums1 和 nums2 全部已排序，不需要与自身元素再比较大小。
nums2[j - 1] < nums1[i] && nums1[i - 1] < nums2[j]
- 做好了这样一个划分以后，中位数就很好找了。偶数情况，中位数是
left_part中的最大与right_part中的最小的均值。奇数情况，中位数是left_part中的最大（因为我们约定把它归到left_part）
median = (max(nums1[i - 1], nums2[j - 1]) + max(nums1[i] + nums2[j])) / 2; // (m + n) % 2 = 0
median = max(nums1[i - 1], nums2[j - 1]) // (m + n) % 2 != 0
- 从1中的等式，我们发现，对于确定的
i，j也被唯一确定。对于两种情况，分别有：
j = (m + n) / 2 - i;
j = (m + n + 1) / 2 - i; // (m + n) % 2 != 0
其实，只需要使用第二个式子表达，因为在偶数情况时，1/2不会起作用，小数部分在代码中会被强取整约掉。
- 所以，本题就转变成了在区间
[0, m]中查找一个合适的i的二分查找问题。算法描述如下：
1. 在区间 [left, right]（初始时，left = 0，right = m） 二分查找一个 i = nums[mid] ，
相应的 j = (m + n + 1) / 2 - i。
2. 检查 left_part 和 right_part 中数的大小关系：
a. nums2[j - 1] < nums1[i] && nums1[i - 1] < nums2[j]
i 符合要求，停止查找，跳到3。
b. nums2[j - 1] > nums1[i]
i 小了，将查找范围调整到 [mid, right]，返回1执行。
c. nums1[i - 1] > nums2[j]
i 大了，将查找范围调整到 [left, mid]，返回1执行。
3. 计算返回中位数。参考思路第二部分。
- 以上是主要思路与步骤，接下来，还得考虑一些特殊情况。
a. 边界问题。即可能出现i = 0,j = 0,i = n,j =m的情况，使得nums1[i - 1],nums2[j - 1],nums1[i],nums[j]参生越界。这四种情况分别表示：将nums1，nums2全部划分到right_part，将nums1,nums2全部划分到left_part。搞清楚这个意义以后，就很好处理了。
例如： 当i = 0时，nums1已经全部划分到right_part，就不必判断nums1[i - 1] < nums2[j]（我们做这个判断的初衷是保证left_part < right_part）。在算中位数的时候，left_part中最大的一定是nums2[j - 1]，而不必再考虑nums[i - 1]，其他同理。
b. left_part和right_part边界数字重复问题。即left_part中最大的数与right_part中最小的数相同，这也很好解决，这种情况下中位数就是这个边界重复数，可以一并划分到符合停止条件。
综上a和b，将4中第2步里的判断条件更改为：
(i == 0 || j == n || nums1[i - 1] <= nums2[j]) && (j == 0 || i == m || nums2[j - 1] <= nums1[i])
解题源码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) return findMedianSortedArrays(nums2, nums1);
int left = 0, right = m;
int i = -1, j = -1;
// 查找合适的i
while (true)
{
i = (left + right) / 2;
j = (m + n + 1) / 2 - i;
if ((i == 0 || j == n || nums1[i - 1] <= nums2[j]) &&
(j == 0 || i == m || nums2[j - 1] <= nums1[i])) {
break;
}
else if (i > 0 && nums1[i - 1] > nums2[j]) {
right = i - 1;
}
else if (j > 0 && nums2[j - 1] > nums1[i]) {
left = i + 1;
}
}
// 计算中位数
int max_left = -1, min_right = -1;
if (i == 0) max_left = nums2[j - 1];// 如果i == 0，left_part中最大的一定是nums2[j - 1]，而不必考虑nums1[i - 1]
else if (j == 0) max_left = nums1[i - 1];
else
{
max_left = max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2) {
return max_left;// i,j的取值符合这个约定：奇数情况，中位数划归到left_part
}
if (i == m) min_right = nums2[j];
else if (j == n) min_right = nums1[i];
else
{
min_right = min(nums1[i], nums2[j]);
}
return double(max_left + min_right) / 2;
}
};
