问题描述：给定两个大小为 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
//思路一：直接合并然后求解，但是不合题意。
//时间复杂度：O(m+n)
//空间复杂度：O(m+n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
int[] nums = new int[len];
int index = 0;
int i = 0;
int j = 0;
while(i<nums1.length && j< nums2.length){
if(nums1[i] < nums2[j]){
nums[index++] = nums1[i++];
}else{
nums[index++] = nums2[j++];
}
}
while(i< nums1.length){
nums[index++] = nums1[i++];
}
while(j< nums2.length){
nums[index++] = nums2[j++];
}
if(len % 2 ==1){
return nums[nums.length/2]*1.0;
}else{
return (nums[nums.length/2] + nums[nums.length/2-1])*1.0 / 2;
}
}
//思路二：
//1、要求时间复杂度 O(log(m+n)),m+n就是两个数组的长度和，又是有序数组，我们很容易想到二分查找
//2、求出的结果是中位数，中位数的特点是其以后的数都比它大，前面的数都比它小。
//3、两个数组都已经是有序数组，
// 因此我们所需要的结果就是num1[start1,end1]中的第i个元素(下标 start1+i-1)和数组num2[start2,end2]中第j个元素(下标 start+j-1)，
///在数组num1[start1,end1]中确定i以及在数组中确定num2[start2,end2]，此时可以采用二分查找的方法，
// 通过不断缩小查找范围来确实所需要查找的值，也符合题目中所要求的分治算法的思想。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int k1 = (len1+len2+1)/2;
int k2 = (len1+len2+2)/2;
//当 (len1+len2)奇数时，此时 k1==k2;
//当 (len1+len2)偶数时，此时 k1+1 == k2
double res =
(findKth(nums1,0,len1-1,nums2,0,len2-1,k1) +
findKth(nums1,0,len1-1,nums2,0,len2-1,k2))/2;
return res;
}
/**
* 查找 nums1[start1,end1] 和 nums2[start2,end2]合并后的第 k 小元素
*/
private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
//计算当前数组范围内的数组长度
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if(len1 > len2){
//这里保持 len1 <= len2,方便后面的操作
return findKth(nums2,start2,end2,nums1,start1,end1,k);
}else if(len1 == 0){
//nums1[start1,start2]数组长度为0，则就是在nums2[start2,end2]中第 k 小的元素
return nums2[start2+k-1];
}else if(k == 1){
//合并后的数组的第1个元素，显然是nums1[start1,end1]和nums2[start2,end2]中第一个元素的较小值
return Math.min(nums1[start1],nums2[start2]);
}
//分治
int i = Math.min(k/2,len1); //在nums1[start1,end1]中第 i 小元素
int j = k - i; //在nums2[start2,end2]中第 j 小元素
if(nums1[start1+i-1] > nums2[start2+j-1]){ //此时 nums2[start2,end2]中就要舍弃前面j个元素
/**
* 使用反证法证明：
* 证：当k/2 >= len1 时，而我们要找的k就在nums2[start2,end2]的前 k/2元素中。
* 我们假设 k 所在的数组下标记为p，那么nums2[start2,end2]中含有的属于后数组前k个元素的元素有(p+1)个。
* 显然，nums1[start1,end1]中必然含有另外 k-(p+1)个元素。
* 由此，得到如下不等式：
* p <= k/2 - 1 （k th 实际所处位置为p，在nums2[start2,end2]的前k/2个元素里。-1是因为现在算的是数组下标，从0开始）
* ==> p + 1 <= k/2；
* ==> k - (p+1) >= k - k/2。
显然，len1 >= k - (p+1) >= k/2 ，这与上面的假设，k/2 >= len1是矛盾的。
*/
return findKth(nums1,start1,end1,nums2,start2+j,end2,k-j); //此时就是求第(k-j)小元素
}else if(nums1[start1+i-1] < nums2[start2+j-1]){ //此时 nums1[start1,end1]中就要舍弃前面i个元素
return findKth(nums1,start1+i,end1,nums2,start2,end2,k-i);
}else{
return nums1[start1+i-1];
}
}
参考：
标签：数组,int,start1,中位数,start2,len1,有序,nums1,nums2 From： https://www.cnblogs.com/i9code/p/18005383