4、寻找两个有序数组的中位数
问题描述
问题分析
题目要求输出合并后的数组的中位数,可以考虑这样的思路:设置两个游标,同时从两个数组从头遍历,依次比较游标所指向元素大小,将较小元素加入新数组中,然后较小元素对应的游标向后移动。当m+n是偶数的时候,游标需要移动(m+n)/2次;当m+n是奇数的时候,游标需要移动(m+n-1)/2次。需要注意的地方是:
1、以上算法不适用于数组为空的情况,需要在此之前做出一些处理。
2、当两个游标所指的元素相等时,需要考虑边界情况。
- 时间复杂度:O( m+n ),游标平均需要移动(m+n)/2次。
- 空间复杂度:O( 1 ), 只需要常数个变量来记录。
Java代码
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
boolean even = true;
int time;
//判断奇偶性
if((m+n)%2 == 0){
time = (m+n)/2;
}else{
time = (m+n-1)/2;
even = false;
}
//nums1空,但nums2不空
if(m == 0){
if(even){
return (nums2[time] + nums2[time-1]) / 2.0 ;
}else{
return nums2[time];
}
}
//nums2空,但nums1不空
if(n == 0){
if(even){
return (nums1[time] + nums1[time-1]) / 2.0 ;
}else{
return nums1[time];
}
}
//nums1不空,nums2不空
int a = 0;
int b = 0;
int[] result = new int[2];
for(int i=0; i<=time; i++){
if(a >= nums1.length){
//a已经走完,b走
++b;
result[i%2] = nums2[b-1];
}else if(b >= nums2.length){
//b已经走完,a走
++a;
result[i%2] = nums1[a-1];
}else{
//a、b都没走完
if(nums1[a] < nums2[b]){
++a;
result[i%2] = nums1[a-1];
}else if(nums1[a] > nums2[b]){
++b;
result[i%2] = nums2[b-1];
}else{
if((a+1) >= nums1.length){
++b;
result[i%2] = nums2[b-1];
}else {
++a;
result[i%2] = nums1[a-1];
}
}
}
}
if(even){
return (result[0] + result[1]) / 2.0 ;
}else{
return result[time%2];
}
}
}
结果分析
以上代码的执行结果:
执行时间 | 内存消耗 |
---|---|
13ms | 54.7 MB |
此题要求的时间复杂度为O(log(m + n)),我以上提出的算法并没有达到要求。其实根据题目中提到了中位数,并且看到log的时候就已经想到了要使用二分的思想。中位数的左边的数都比它小,右边的数都比它大。但是其中具体的算法还有待商榷。