给定两个大小分别为 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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
if(((n + m) & 1) == 0) {
return ((double) findKthNum(nums1,nums2, (n+m)>>1) + (double) findKthNum(nums1, nums2, ((n+m)>>1) +1)) / 2;
} else {
return findKthNum(nums1, nums2, ((n+m+1)>> 1));
}
}
/**
* 从给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2
* 返回第k大的数
* @param nums1
* @param nums2
* @param k
* @return
*/
public static int findKthNum(int[] nums1, int[] nums2, int k) {
//如果某个数组为空，则返回另外一个数组的第k个数（下标为k-1）
if(nums1.length == 0 || nums2.length == 0) {
return nums1.length == 0? nums2[k - 1] : nums1[k-1];
}
//如果两者都不为空，继续，假设
//k有三种可能性，1:小于等于短数组的长度 2.长度大于短数组长度，小于等于长数组长度 3.大于长数组长度小于两个数组长度之和
int[] shortArr = nums1.length < nums2.length? nums1 : nums2;
int[] longArr = shortArr == nums1? nums2 : nums1;
//1:小于等于短数组的长度
if(k <= shortArr.length) {
return getUpMiddle(shortArr, longArr, 0, k-1, 0, k-1);
//2.长度大于短数组长度，小于等于长数组长度
} else if(k > shortArr.length && k <= longArr.length) {
//这种情况短数组各个位置都有可能，长数组的大于k的位置和小于k-m的位置没有可能
//这样的话短数组剩余m个，长数组剩余n-(k-m-1)-(k-n)=2n-2k+m+1
if(longArr[k-1-shortArr.length] >= shortArr[shortArr.length - 1]) {
return longArr[k-1-shortArr.length];
}
return getUpMiddle(shortArr, longArr, 0, shortArr.length - 1, k-shortArr.length, k - 1);
//3.大于长数组长度小于两个数组长度之和
} else {
//这种情况的话，longArr中需要淘汰第1~k-m-1(下标0~k-m-2)这些
//而shortArr里需要淘汰第1~k-n-1(下标0~k-n-2)这些，两个数组的剩余长度都是m+n-k个(long从k-m到结尾,short从k-n到结尾)
if(longArr[k-1 - shortArr.length] >= shortArr[shortArr.length - 1]) {
return longArr[k-1 - shortArr.length];
} else if(shortArr[k-1 - longArr.length] > longArr[longArr.length - 1]) {
return shortArr[k-1 - longArr.length];
}
return getUpMiddle(shortArr,longArr, k-longArr.length, shortArr.length-1, k - shortArr.length, longArr.length-1);
}
}
private static int getUpMiddle(int[] nums1, int[] nums2, int start1, int end1, int start2, int end2) {
int mid1 = 0;
int mid2 = 0;
while(start1 < end1) {
mid1 = (start1 + end1) >> 1;
mid2 = (start2 + end2) >> 1;
//如果两个区间的中位数相等，这个就是我们要的值
//每个数组的长度是奇数的情况下，这两个数就是上中位数和下中位数
if(nums1[mid1] == nums2[mid2]) {
return nums1[mid1];
}
//如果不相等，那有两种情况：1.数组的区间长度为奇数 2.数组的区间长度为奇数
// nums1的中位数大 或者nums2的中位数大
//如果长度为偶数，这个比较简单，找到对应的区间继续取中位数
if(((end1 - start1 + 1) & 1) == 0) {
if(nums1[mid1] > nums2[mid2]) {
end1 = mid1;
start2 = mid2 + 1;
} else {
end2 = mid2;
start1 = mid1 + 1;
}
} else {
if(nums1[mid1] > nums2[mid2]) {
//这个时候我们可以排除num1从mid1到end1是上中位数的可能性
//同时也可以排除num2从start2到mid2-1是上中位数的可能性
//一共排除了一半的数，这个时候我们只需要从剩下的数中找到
//但是剩下的数是奇数个（原来的区间长度，nums2现在多一个）
//现在尝试排除mid2,如果大于nums1[mid1 - 1]，则nums[mid2]就是我们要找的
if(nums2[mid2] >= nums1[mid1 - 1]) {
return nums2[mid2];
}
//如果nums2[mid2]不大于nums1[mid1 - 1]，则nums2[mid2]不可能是上中位数
//现在就是在nums1的start1~mid1-1和nums2的mid2+1~end2就是我们要考虑的范围
//求中位数即可
end1 = mid1 - 1;
start2 = mid2 + 1;
} else {
//同上
if(nums1[mid1] >= nums2[mid2 - 1]) {
return nums1[mid1];
}
end2 = mid2 - 1;
start1 = mid1 + 1;
}
}
}
return nums1[start1] > nums2[start2]? nums2[start2] : nums1[start1];
}
}