【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];
        }
    }
}

        

          
        
        
        

          

          AI 代码解读