给定两个大小分别为 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
-106 <= nums1[i], nums2[i] <= 106
解法一
简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}时间复杂度：遍历全部数组(m+n)
空间复杂度：开辟了一个数组，保存合并后的两个数组O(m+n)
解法二
其实，我们不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了。
开始的思路是写一个循环，然后里边判断是否到了中位数的位置，到了就返回结果，但这里对偶数和奇数的分类会很麻烦。当其中一个数组遍历完后，出了for循环对边界的判断也会分几种情况。总体来说，虽然复杂度不影响，但代码会看起来很乱。
首先是怎么将奇数和偶数的情况合并一下。
用len表示合并后数组的长度，如果是奇数，我们需要知道第（len+1）/2个数就可以了，如果遍历的话需要遍历int(len/2 ) + 1次。如果是偶数，我们需要知道第len/2和len/2+1个数，也是需要遍历len/2+1次。所以遍历的话，奇数和偶数都是len/2+1次。
返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量left和right，right保存当前循环的结果，在每次循环前将right的值赋给left。这样在最后一次循环的时候，left将得到right的值，也就是上一次循环的结果，接下来right更新为最后一次的结果。
循环中该怎么写，什么时候A数组后移，什么时候B数组后移。用aStart和bStart分别表示当前指向A数组和B数组的位置。如果aStart还没有到最后并且此时A位置的数字小于B位置的数组，那么就可以后移了。也就是aStart＜m&&A[aStart]<B[bStart]。
但如果B数组此刻已经没有数字了，继续取数字B[ bStart ]，则会越界，所以判断下bStart是否大于数组长度了，这样||后边的就不会执行了，也就不会导致错误了，所以增加为aStart＜m&&(bStart)>=n||A[aStart]<B[bStart])。
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
}时间复杂度：遍历len/2+1次，len=m+n，所以时间复杂度依旧是O(m+n)。
空间复杂度：我们申请了常数个变量，也就是m，n，len，left，right，aStart，bStart以及i。
总共 8 个变量，所以空间复杂度是O(1）。
解法三
我们首先理一下中位数的定义是什么
中位数（又称中值，英语：Median），[统计学] (https://baike.baidu.com/item/%E7%BB%9F%E8%AE%A1%E5%AD%A6/2630438)中的专有名词，代表一个样本、种群或[概率分布] (https://baike.baidu.com/item/%E6%A6%82%E7%8E%87%E5%88%86%E5%B8%83/828907)中的一个数值，其可将数值集合划分为相等的上下两部分。
所以我们只需要将数组进行切。
一个长度为 m 的数组，有 0 到 m 总共 m + 1 个位置可以切。
我们把数组 A 和数组 B 分别在 i 和 j 进行切割。
将 i 的左边和 j 的左边组合成「左半部分」，将 i 的右边和 j 的右边组合成「右半部分」。
当 A 数组和 B 数组的总长度是偶数时，如果我们能够保证
*左半部分的长度等于右半部分
i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
*左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位数就可以表示如下
（左半部分最大值 + 右半部分最小值 ）/ 2。
（max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2
当 A 数组和 B 数组的总长度是奇数时，如果我们能够保证
*左半部分的长度比右半部分大 1
i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
*左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位数就是
左半部分最大值，也就是左半部比右半部分多出的那一个数。
max ( A [ i - 1 ] , B [ j - 1 ]）
上边的第一个条件我们其实可以合并为j=(m+n+1)/2−i，因为如果m+n是偶数，由于我们取的是int值，所以加1也不会影响结果。当然，由于0<=i<=m，为了保证0<=j<=n，我们必须保证m<=n。
m≤n,i<m,j=(m+n+1)/2−i≥(m+m+1)/2−i>(m+m+1)/2−m=0
m≤n,i>0,j=(m+n+1)/2−i≤(n+n+1)/2−i<(n+n+1)/2=n
最后一步由于是 int 间的运算，所以1/2=0。
而对于第二个条件，奇数和偶数的情况是一样的，我们进一步分析。为了保证 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]）），因为 A 数组和 B 数组是有序的，所以 A [ i - 1 ] <= A [ i ]，B [ i - 1 ] <= B [ i ] 这是天然的，所以我们只需要保证 B [ j - 1 ] < = A [ i ] 和 A [ i - 1 ] <= B [ j ] 所以我们分两种情况讨论：
B [ j - 1 ] > A [ i ]，并且为了不越界，要保证 j != 0，i != m
此时很明显，我们需要增加 i ，为了数量的平衡还要减少 j ，幸运的是 j = ( m + n + 1) / 2 - i，i 增大，j 自然会减少。
A [ i - 1 ] > B [ j ] ，并且为了不越界，要保证 i != 0，j != n
此时和上边的情况相反，我们要减少 i ，增大 j 。
上边两种情况，我们把边界都排除了，需要单独讨论。
当 i = 0, 或者 j = 0，也就是切在了最前边。
此时左半部分当 j = 0 时，最大的值就是 A [ i - 1 ] ；当 i = 0 时 最大的值就是 B [ j - 1] 。右半部分最小值和之前一样。
当 i = m 或者 j = n，也就是切在了最后边。
此时左半部分最大值和之前一样。右半部分当 j = n 时，最小值就是 A [ i ] ；当 i = m 时，最小值就是B [ j ] 。
所有的思路都理清了，最后一个问题，增加 i 的方式。当然用二分了。初始化 i 为中间的值，然后减半找中间的，减半找中间的，减半找中间的直到答案。
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
return findMedianSortedArrays(B,A); // 保证 m <= n
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
iMin = i + 1;
}
else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要减小
iMax = i - 1;
}
else { // 达到要求，并且将边界条件列出来单独考虑
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
}
}
return 0.0;
}
}时间复杂度：我们对较短的数组进行了二分查找，所以时间复杂度是O(log（min（m，n））。
空间复杂度：只有一些固定的变量，和数组长度无关，所以空间复杂度是O(1)。