2021-5-4 第四天第四题

寻找两个正序数组的中位数

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

输入:nums1 = [], nums2 = [1]
输出:1.00000

输入:nums1 = [2], nums2 = []
输出:2.00000

Version1:这是自己第一次顺畅的,没有修改的,一次性写对的算法题,骄傲

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    //整体思路:将nums1和nums2中的值赋值到一个新的数组,新数组的大小为原来两数组长度的和。从新得到的数组中就很容易得到中位数了。
    int len1=nums1.length;
    int len2=nums2.length;
    int len=len1+len2;
    int[] arr=new int[len];
    //定义两个指针:start1和start2,start1表示数组1的移动下标,start2表示数组2的移动下标
    int start1=0;
    int start2=0;
    //ans表示最终的结果:中位数
    double ans=0;
    for(int i=0;i<len;i++){
        if(start1<len1&&start2<len2){//数组1和数组2都没有到最后
            if(nums1[start1]<=nums2[start2]){//根据start1和start2位置数的大小,确定将那个数                                                插入到新数组中,并将指针移动到下一个位置。
                arr[i]=nums1[start1];
                start1++;
            }else{
                arr[i]=nums2[start2];
                start2++;
            }
        }else if(start1<len1){//数组2已经遍历完成了,将数组1剩余的值复制到新数组中
            arr[i]=nums1[start1];
            start1++;
        }else{//数组1已经遍历完成了,将数组2剩余的值复制到新数组中
            arr[i]=nums2[start2];
            start2++;
        }
    }
    if(len%2==1){
        ans=arr[len/2];
    }else{
        ans=(arr[len/2-1]+arr[len/2])/2.0;
    }
    return ans;
}

执行用时:3 ms, 在所有 Java 提交中击败了82.29% 的用户

内存消耗:39.5 MB, 在所有 Java 提交中击败了88.64% 的用户

Version2

待续。。。

上一篇:算法刷题:深入分析一下我和大佬的差距


下一篇:最长公共子序列