【LeetCode04寻找两个正序数组的中位数】
01.题目简介:
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n))
案例
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
02.思路解释:
我们可以看出题目会给我们两个有序数组 然后合成一个有序数组 并且要求我们需要时间复杂度达到O(log (m+n))的水平,所以我们应该关注的是如何合并,我的思路是归并排序 也是一个比较常规的想法 因为归并排序的时机复杂度是O($nlogn$)的水平 其中归并排序的每一次的时间复杂度是O(n) 层数是O($logn$),由于我们题目已经给了我们两个有序的数组,所以我们只需要一次归并排序 但这种方法时间复杂度是O(m+n) 不满足要求 不过我这样也过了,官方数据不强,如果满足O(log (m+n))应该是要要求二分优化的 等我回头再做的时候进行优化补充。
03.代码:
class Solution
{
public static int[] msort(int[] q,int l,int mid,int r){// 归并排序
int i=l,j=mid+1;
int k=0;
int[] temp=new int[q.length];
while(i<=mid&&j<=r){
if(q[i]<q[j]){
temp[k++]=q[i++];
}
else{
temp[k++]=q[j++];
}
}
while(i<=mid){
temp[k++]=q[i++];
}
while(j<=r){
temp[k++]=q[j++];
}
return temp;
}
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int mid=nums1.length;
int r=nums2.length;
int[] temp=new int[mid+r];
int k=0;
for(int i=0;i<mid;i++)
temp[k++]=nums1[i];
for(int i=0;i<r;i++)
temp[k++]=nums2[i];
temp=msort(temp,0,mid-1,mid+r-1);
if((mid+r)%2==0){
double res=((double)temp[(mid+r-1)/2]+(double)temp[(mid+r-1)/2+1])/2;
return res;
}
else {
return temp[(mid+r-1)/2];
}
}
}