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

描述

leetcode 官方第 4 题。给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

示例1:

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

示例2:

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

示例3:

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

示例4:

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

示例5:

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

思路

这边我们可以考虑将两个数组合并，然后求合并后的数组的中位数。因为它的合并前的两个数据都是有序排序的。

下面是两个数组的和长度是奇数：

因为数组 1 和 数组 2 是有序的数组，所以我们新定义一个数组，将两个数组内容按照顺序存放在该数组里面，然后取出中位数。因为是奇位数，所以就取中间的数 3/2 = 1。即返回 2。因为数组是从 0 索引开始。

下面我们再以一个长度是偶数的例子：

我们可以看到，合并后的数组是偶数长度，它的长度是 4。4/2 = 2。所以我们需要取 2-1 这个索引的数和 2 这个索引的数。然后相加除以 2.0。如果不除以 2.0 系统会默认认为是整数类型。

代码具体实现

Java语言版本

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //数组1的长度
        int nums1Length = nums1.length;
        //数组2的长度
        int nums2Length = nums2.length;
        //最终数组的总长度
        int returnNumsLength = nums1Length + nums2Length;
        //定义一个最终数组
        int[] retNums = new int[returnNumsLength];
        //遍历到的数据1的索引初始值
        int nums1Index = 0;
        //遍历的索引2的索引初始值
        int nums2Index = 0;
        //表示 num1 是否遍历完
        boolean nums1EndFlag = false;
         //表示 num2 是否遍历完
        boolean nums2EndFlag = false;
        for(int i=0;i<returnNumsLength ;i++){
            int tmpNum1 = 0;
            if(nums1Index <= nums1Length -1){
                tmpNum1 = nums1[nums1Index];
            }else{
               //表示已经数组1已经被遍历结束
               nums1EndFlag = true; 
            }
            int tmpNum2 = 0;
            if(nums2Index <= nums2Length-1){
                tmpNum2 = nums2[nums2Index];
            }else{
                //表示数组2已经遍历结束
                nums2EndFlag = true;
            }
            //如果数组1被遍历结束了，将数组2的数据获取直接赋值
            if(nums1EndFlag){
                 retNums[i] = tmpNum2;
                 nums2Index ++;
                 continue;
            }
            //如果数组2被遍历结束了，将数组1的数据直接赋值给返回数组
            if(nums2EndFlag){
               retNums[i] = tmpNum1;  
               nums1Index ++;
               continue;
            }
            if(tmpNum1 >= tmpNum2){
                retNums[i] = tmpNum2;
                nums2Index ++;
            }else{
                retNums[i] = tmpNum1;
                nums1Index ++;
            }
        }
       //特殊情况，数组长度为1
       if(returnNumsLength == 1){
           return retNums[0];
       }
       if(returnNumsLength % 2 == 0){
           int num1 = retNums[returnNumsLength/2];
           int num2 = retNums[returnNumsLength/2 - 1 ];
           return (num1 + num2)/2.0;
       }else{
           return retNums[returnNumsLength / 2];
       }
    }
}

Go语言版本

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
        //数组1的长度
        nums1Length := len(nums1)
        //数组2的长度
        nums2Length := len(nums2)
        //最终数组的总长度
        returnNumsLength := (nums1Length + nums2Length)
        //定义一个最终数组
        retNums :=  make([]int, returnNumsLength)
        //遍历到的数据1的索引初始值
        nums1Index := 0
        //遍历的索引2的索引初始值
        nums2Index := 0
        //表示 num1 是否遍历完
        nums1EndFlag := false
         //表示 num2 是否遍历完
        nums2EndFlag := false
        for i := 0;i<returnNumsLength;i++{
            tmpNum1 := 0
            if nums1Index <= nums1Length -1{
                tmpNum1 = nums1[nums1Index]
            }else{
               //表示已经数组1已经被遍历结束
               nums1EndFlag = true
            }
            tmpNum2 := 0
            if nums2Index <= nums2Length-1{
                tmpNum2 = nums2[nums2Index]
            }else{
                //表示数组2已经遍历结束
                nums2EndFlag = true
            }
            //如果数组1被遍历结束了，将数组2的数据获取直接赋值
            if nums1EndFlag{
                 retNums[i] = tmpNum2
                 nums2Index ++
                 continue
            }
            //如果数组2被遍历结束了，将数组1的数据直接赋值给返回数组
            if nums2EndFlag {
               retNums[i] = tmpNum1 
               nums1Index ++
               continue
            }
           if tmpNum1 >= tmpNum2 {
                retNums[i] = tmpNum2
                nums2Index ++
            }else{
                retNums[i] = tmpNum1
                nums1Index ++
            }
        }
        //特殊情况，数组长度为1
       if returnNumsLength == 1{
           return float64(retNums[0])
       }
       if returnNumsLength % 2 == 0 {
           num1 := retNums[returnNumsLength/2]
           num2 := retNums[returnNumsLength/2 - 1 ]
           return (float64(num1) + float64(num2))/2.0;
       }else{
           return float64(retNums[returnNumsLength / 2])
       }
}