找出两个有序数组的整体中位数
输入： 两个有序数列
输出： 总体数列的中位数
要求 时间复杂度 O(log(m+n))
用例： [1,3] [2] ====> The median is 2.0
[1,2] [3,4] ====> The median is 2.5
分析
这个题目要求了时间复杂度。如果不要求时间复杂度，可以直接放到一个整体的数列中，然后用一个排序算法，之后就是一个有序数列的中位数。
但是，要求时间复杂度是 log 形式的，所以一定是分治法。
思路
依旧按照之前的将两个有序数列合为一个有序数列的方法。考虑时间复杂度。
a[n] ①②③...
b[m] ①②③...
c[m+n]
比较 第一个数列的第一个数字和第二个数列的第一个数字，将小的放进新的数列的第一个，知道某一个数列全部没有，之后将另外一个数列剩下的放在后面。即得到了第三个有序数列。
这个方法比官方的解法简洁很多
代码
package day_1;
public class FindMedianSortedArray {
public double solution(int nums1[], int nums2[]){
int m = nums1.length;
int n = nums2.length;
int a[] = new int[m+n];
int i=0,j=0,k=0;
for (i=0,j=0,k=0;i<m&&j<n;k++){
if (nums1[i]<nums2[j]){
a[k] = nums1[i++];
} else{
a[k] = nums2[j++];
}
}
if(i == m){ // 这是说上面的数列先完了，就把下面的排在后面
while(j<n){
a[k++] = nums2[j++];}
}
if(j == n){ // 下面的数列先完了
while(i<m){
a[k++] = nums1[i++];
}
}
// 到这里就从小到大排列完了，之后找中位数就好
int count=k;
int mid=count/2;
if(count%2==0&&mid>0){
return (a[mid-1]+a[mid])*0.5;
}
else
return a[mid]*1.0;
}
public static void main(String[] args){
int a[] = {1,3};
int b[] = {2};
int c[] = {1,2};
int d[] = {3,4};
FindMedianSortedArray test = new FindMedianSortedArray();
System.out.println("The median is "+ test.solution(a,b));
System.out.println("The median is "+ test.solution(c,d));
}
}
