这几天在看Jetpack全家桶，被搞的有点自闭，没时间到LeetCode上玩耍，晚上在看的官方的demo的时候，yyb滴滴了我一下
？看什么看，看Jetpack全家桶不好吗？？？
好吧既然余总叫小的看一下，我就看看吧
这...怎么这模板这么眼熟，果然，在LeetCode上找到了他嘴里的她，于是就有了下面的故事...
寻找两个有序数组的中位数
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
示例：
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
提示：你可以假设 nums1 和 nums2 不会同时为空。
题目分析
解法一：
因为中位数是有序数组中间的那个数（或者两个数的平均数），而题目明确是求两个有序数组的中位数，这就很容易就想到将两个有序数组归并，然后求出他们的中位数；
两个有序数组合并的时间复杂度是O(M+N)，显然不符合题目的要求，但是提交上去竟然过了；
注：解法一里用了栈来收集前n/2的数字，到达中位数的时候停下来，返回
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1=0;
int len2=0;
int len=nums1.length+nums2.length;
Stack<Integer> stack=new Stack<>();
while(stack.size()<=len/2) {
if (len1 < nums1.length && len2 < nums2.length) {
if (nums1[len1] <= nums2[len2]) {
stack.push(nums1[len1++]);
System.out.println(nums1[len1-1]);
} else {
stack.push(nums2[len2++]);
System.out.println(nums2[len2-1]);
}
} else if (len1 == nums1.length) {
stack.push(nums2[len2++]);
System.out.println(nums2[len2-1]);
} else if (len2 == nums2.length) {
stack.push(nums1[len1++]);
System.out.println(nums1[len1-1]);
}
}
if(len%2==0){
double a=stack.pop();
double b=stack.pop();
return ((a+b)/2);
}else{
return (double)(stack.pop());
}
}
解法二：
看到log，其实我们想到的应该是二分， 下面我用图解的方式更好的展示一下二分的思路
-
这是原始状态的数组，满足题目中的两个有序数组的条件
1 -
分别将两个数组砍成两半，现在假设两个左边是合并有序数组的左边，两个右边是合并有序数组的右边，有序数组显然有这样的性质：左边的数小于右边的数，现在我们验证一下我们的假设时候满足这样的性质
2 -
验证：我们先找出左边最大的数，它是5，再找出右边最小的数，它是2，显然不满足有序数组的性质，这可怎么办呢？快排里有个很重要的思想，就是给每一个数找到属于它的位置，我们这里可以受快排的启发，给不符合性质的数找到属于它的位置：把5放到右边去，把2放到左边去！
3 -
现在数组变成这个样子，左边最大的是2，右边最小的是5，显然满足题目的意思
4 -
3和4是一种情况，是上面数组的左边大于下面数组的右边，还有另一种情况，就是下面数组的左边大于上面数组的右边，如下所示：
5 -
对于5的情况，做法和（3、4）差不多，将3放到左边，将5放到右边，这样假设就成立了！
6
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//确保num1比nums2要短
if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
//特殊情况的处理，短的为空，直接返回长的中位数
if (nums1.length == 0)
if( nums2.length % 2 == 0)
return (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0;
else
return nums2[nums2.length / 2];
//将短的数组分成两半，长的数组也分成两半，
//左边的大小 = 右边的大小（总长度为偶数） 或者左边大小 = 右边大小 - 1（总长度为奇数）
int divide1 = nums1.length / 2;
int divide2 = (nums1.length + nums2.length) / 2 - divide1;
while (true) {
//短的数组全都分到左边去
if (divide1 == nums1.length) {
//讨论奇偶数情况
if ((nums1.length + nums2.length) % 2 == 0) {
//特殊情况：长的数组全都分到右边去
if (divide2 != 0)
return ((double) (Math.max(nums1[divide1 - 1], nums2[divide2 - 1]) + nums2[divide2])) / 2;
return (double) (nums1[divide1 - 1] + nums2[divide2]) / 2;
} else {
return (double) nums2[divide2];
}
}
//找出左边最大的和右边最小的
int maxLeft, minRight;
//短的全在右边
if (divide1 == 0)
maxLeft = nums2[divide2 - 1];
else
maxLeft = Math.max(nums1[divide1 - 1], nums2[divide2 - 1]);
//长的全在左边
if (divide2 == nums2.length)
minRight = nums1[divide1];
else
minRight = Math.min(nums1[divide1], nums2[divide2]);
//符合假设，直接返回
if (minRight >= maxLeft)
if ((nums1.length + nums2.length) % 2 == 0)
return ((double) (minRight + maxLeft)) / 2;
else
return (double) minRight;
// 不符合假设，左边最大的右移，右边最小的左移
// 分别对应上右<下左 || 下右<上左
if (nums1[divide1] <= nums2[divide2 - 1]) {
divide1++;
divide2--;
} else {
divide1--;
divide2++;
}
}
}
