（LeetCode）Java 求解寻找两个正序数组的中位数

- 日理万妓 2022-12-20 02:53 141阅读 0赞

### 文章目录 ###

*   *  一、题解
     *  二、代码一
     *  三、代码二
     *  四、总结

## 一、题解 ##

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

第一种简单方法可以直接合并两个数组，然后对数组排序，再根据数组长度的奇偶性返回结果即可

第二种方式，不需要合并数组，length 表示合并后数组的长度，如果是奇数我们只需要知道 ( l e n g t h + 1 ) / 2 (length+1)/2 (length\+1)/2 个数即可，如果是偶数，我们需要知道 l e n / 2 len/2 len/2 和  l e n / 2 + 1 len/2+1 len/2\+1 个数，所以也需要遍历  l e n / 2 + 1 len/2+1 len/2\+1 次  
返回中位数，奇数只需要返回最后一次的遍历结果，如果是偶数，则需要返回最后一次和上一次的遍历结果

## 二、代码一 ##

class Solution { 
        public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
            // 创建数组
            int[] num = new int[nums1.length+nums2.length];
            // 合并数组
            for(int i=0;i<nums1.length;i++){ 
                num[i] = nums1[i];
            }
            for(int i=0;i<nums2.length;i++){ 
                num[nums1.length+i] = nums2[i];
            }
            // 数组排序
            Arrays.sort(num);
            // 根据奇偶返回值
            if(num.length%2==0){ 
                return (num[num.length/2]+num[num.length/2-1])/2.0;
            }
            return num[num.length/2];
        }
    }

## 三、代码二 ##

import java.util.*;
    
    public class Test { 
        public static void main(String[] args) { 
            int[] nums1 = { 1, 3};
            int[] nums2 = { 2};
            double result = findMedianSortedArrays(nums1, nums2);
            System.out.println(result);
        }
    
        private static double findMedianSortedArrays(int[] nums1, int[] nums2) { 
            //记录总长度
            int length = nums1.length + nums2.length;
            //p表示最后的访问数字，pre 表示最后的上一个数字
            int pre = -1, p = -1;
            //表示nums1和nums2的数组下标
            int start1 = 0, start2 = 0;
            //遍历到 length/2 即可
            for (int i = 0; i <= length / 2; i++) { 
                pre = p;
                //nums1对应的数字小于nums2,或者 nums2 已经访问到头
                if (start1 < nums1.length && (start2 >= nums2.length || nums1[start1] < nums2[start2])) { 
                    p = nums1[start1++];
                } else if (start2 < nums2.length) { 
                    p = nums2[start2++];
                }
            }
            return ((length & 1) == 0) ? (p + pre) / 2.0 : p;
        }
    }

## 四、总结 ##

1.  数组的初始化

// 创建数组
    int[] num = new int[nums1.length+nums2.length];

1.  数组的排序：Arrays.sort(num);
2.  高效判断奇偶：二进制判断

(length & 1) == 0：表示偶数
    (length & 1) == 1：表示奇数

1.  三目运算：`return ((length & 1) == 0) ? (p + pre) / 2.0 : p;`
2.  返回double：`(p+pre)/2.0`，注意这里的是 2.0