给定两个大小为 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
第一个解题思路来自于归并排序的合并相邻有序子序列，因为两个数组都是有序的，所以可以分别从nums1和nums2的头开始遍历，将两个数组中较小的数填进新的数组merge。最后，根据两个数组的长度之和，分奇偶两种情况得到新数组的中位数。
这个方案思路比较简单，代码见MainClass1.java
时间复杂度：因为两个数组都是有序的，所以合并数组实际上就是遍历了两个数组，所以时间复杂度为 O(m+n) ，没有满足 O(log(m + n))的要求。
空间复杂度：因为开辟了一个merge数组，所以空间复杂度为O(m+n)。
在方案1中，对两个数组的所有元素都进行了遍历，但是其实只需要遍历到中位数的位置就可以停止遍历，也不需要再建立一个数组。
但是要注意的是：
当两个数组长度之和为奇数的时候，只需要找到第(m+n+1)/2个数最小的数即可；
当两个数组长度之和为偶数的时候，不仅要找到第(m+n)/2个最小的数，还需要找到第(m+n)/2+1个数。
为了避免逻辑的复杂性，无论奇数还是偶数都遍历到(m+n+1)/2+1的位置，用left记录上一次的较小值，right记录当前的较小值。遍历结束的时候，奇数返回left，偶数返回(left+right)/2即可。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m=nums1.length, n=nums2.length;
int i=0, j=0, left=0, right=0;
//特殊情况，一个为空，另一个只有一个数
if (m==0) right=nums2[0];
else if (n==0) right=nums1[0];
while (i < m || j < n) {
left = right;
//这里的逻辑是这样考虑的，一共四种情况，合并之后只有两个情况是i++：
//1. n1有数，n2有数，n1<n2，i++
//2. n1有数，n2有数，n1>n2，j++
//3. n1有数，n2无数（遍历完了），i++
//4. n1无数，n2有数，j++
if ((j == n) || (i < m && j < n && nums1[i] <= nums2[j])) right = nums1[i++];
else right = nums2[j++];
if (i + j == (m + n + 1) / 2 + 1) break;
}
if ((m+n) % 2==0) return (double)(left+right)/2;
else return (double)left;
}时间复杂度：整个过程遍历了(m+n+1)/2+1个数，所以时间复杂度还是为 O(m+n) ，没有满足 O(log(m + n))的要求。
空间复杂度：只用了两个变量记录较小值，空间复杂度为O(1)。
方案1和2都没有达到题目要求的 O(log(m + n)) 时间复杂度，很明显对数时间复杂度在暗示二分查找，那么二分查找的着手点是什么呢？
换一种思路去思考这个问题，其实是在找两个有序数组中的第k个最小的数，而k=(m+n/2)，那么方案2中所做的事情就可以理解成，不断排除不可能是第k个最小的数的数字（每次排除一个），那么可不可以每次排除多一点呢？所以思路就出现了，为了方便解释，我就用两组数据进行直观的操作：
假设：n1=[1,3,5,7,9,11]，n2=[2,4,6,8,10,12]，则要找到第6个最小的数。
要找到第6个最小的数，就是排除前5个最小的数，这里就可以用到折半的思想，因为两个数组都是有序的，所以每次可以排除k/2个数。下面将模拟运算过程。
k=6 (可以排除6/2=3个数)
n1=[1,3,5,7,9,11]
↑
n2=[2,4,6,8,10,12]
↑
此时n1第3个数为5，n2第3个数为6，5<6，所以一定可以说，[1,3,5]肯定是前5个最小的数里面的成员，将它们排除，k=6-3=3。
k=3 (可以排除3/2=1个数)
n1=[7,9,11]
↑
n2=[2,4,6,8,10,12]
↑
此时n1第1个数为7，n2第1个数为2，7>2，所以一定可以说，[2]肯定是前3个最小的数里面的成员，将它排除，k=3-1=2。
k=2 (可以排除2/2=1个数)
n1=[7,9,11]
↑
n2=[4,6,8,10,12]
↑
此时n1第1个数为7，n2第1个数为4,7>4，所以一定可以说，[4]肯定是前2个最小的数里面的成员，将它排除，k=2-1=1。
当k=1时，即我们已经排除了前5个最小的数，剩下序列中的最小数即是我们要找的第六个最小的数。所以k=1即为运算的边界条件，当k=1时我们就可以退出折半查找的过程。方案3的思路和方案2在本质上都是一致的，即排除掉所有不可能是第k个最小的数，那么剩下的最小数就一定是第k个最小的数，代码如下：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int k = (m + n) / 2;
int i = 0, j = 0;
int left = 0, right = 0;
while (k > 1) {
i += k / 2 - 1;
j += k / 2 - 1;
if ((j >= n) || (i < m && j < n && nums1[i] <= nums2[j])) {
j -= k / 2 - 1;
i++;
} else {
i -= k / 2 - 1;
j++;
}
k -= k / 2;
}
//已经排除掉前（m+n）/2-1个数
if ((j >= n) || (i < m && j < n && nums1[i] < nums2[j])) left = nums1[i++];
else left = nums2[j++];
if ((j >= n) || (i < m && j < n && nums1[i] < nums2[j])) right = nums1[i++];
else right = nums2[j++];
if ((m + n) % 2 == 1) return (double) right;
else return (double)(left + right) / 2;
}时间复杂度：因为每一次都排除掉k/2个数，所以整个算法的时间复杂度为 logk ，也就是 log((m+n)/2)，满足了 O(log(m+n)) 的时间复杂度要求。
空间复杂度：只用了两个变量记录较小值，空间复杂度为O(1)。