4. Median of Two Sorted Arrays
- Total Accepted: 104147
- Total Submissions: 539044
- Difficulty: Hard
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5 其实整个思路应该就是将两个有序数组进行排序的过程，然后根据总个数的奇偶决定中位数是一个还是两个的平均值。
public class No_4 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length ;
int [] res ;
//判断最后的结果是单独一个数还是两个数的平均值
if(total%2 == 1){
res = new int [1] ;
}else{
res = new int [2] ;
}
int count = 0 ; //当前值是第count小的数
int i = 0 ; //nums1的下标
int j = 0 ; //nums2的下标
int k = 0 ; //res的下标
int min ;
/*
* 将两个有序数组进行排序的过程
* 当total为偶数时，结果为总数的第 （total-1）/2+1个数和第（total-1）/2+2个数
* 当total为基数时，结果为总数的第（total-1）/2+1个数
* 所以，当count > （total-1）/2 时，开始存储，直到res存满为止
*/
while((i < nums1.length ) && (j < nums2.length) && (k < res.length)){
count++ ;
min = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++] ;
if(count > (total-1)/2){
res[k++] = min ;
}
}
//考虑nums2先排除完而没有完全得到需要的结果的情况
while((i < nums1.length ) && (k < res.length)){
count++ ;
min = nums1[i++] ;
if(count > (total-1)/2){
res[k++] = min ;
}
}
//考虑nums1先排除完而没有完全得到需要的结果的情况
while((j < nums2.length ) && (k < res.length)){
count++ ;
min = nums2[j++] ;
if(count > (total-1)/2){
res[k++] = min ;
}
}
//返回结果
if(total%2 == 1){
return res[0] ;
}else{
return ((res[0] + res[1])/2.0) ;
}
}
}