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

题目描述

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

思路分析（简单做法--> 归并 + 排序）

1. 将两个数组中的元素分别添加到ArrayList集合中
2. 对集合中的元素进行排序
3. 寻找中位数

源码及分析

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        //思路：归并+排序
        //记录两个数组的长度
        int len1 = nums1.length;
        int len2 = nums2.length;
        //记录两个数组的和
        int len = len1 + len2;
        //记录返回的结果
        double res;

        //创建ArrayList集合保存两个数组的元素
        ArrayList<Integer> list = new ArrayList<>();
        //遍历数组1添加元素到集合
        for (int i = 0; i < len1; i++) {
            list.add(nums1[i]);
        }
        //遍历数组2添加元素到集合
        for (int i = 0; i < len2; i++) {
            list.add(nums2[i]);
        }
        //调用Comparator接口对集合中的元素进行从小到大排序
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        //根据集合元素数量的奇偶判断中位数的位置
        if (len % 2 == 1){
            res = list.get(len / 2);
        }else {
            res =( list.get(len / 2) + list.get(len / 2 - 1)) / 2.0;
        }
        //返回
        return res;
    }