本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

前言

力扣第四题如下所示：

在这里插入图片描述

一、思路

这一题从题目可得知以下两个信息

输入：两个数组（正序）
输出：中位数

那么最简单的思路就是将两个数组合并到一个数组，取中位数即可

二、实现

代码实现

完整代码如下所示：

    /**
     * 归并
     * 时间复杂度O(m+n)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] arr = new int[nums1.length + nums2.length];
        int index1 = 0;
        int index2 = 0;
        for (int i=0; i<arr.length; i++) {
            // 比较两个数组的元素，谁小谁进
            if (index2 == nums2.length || (index1 < nums1.length && nums1[index1] <= nums2[index2])) {
                arr[i] = nums1[index1];
                index1 ++;
            } else {
                arr[i] = nums2[index2];
                index2++;
            }
        }
        // 获取中位数
        if (arr.length % 2 == 0) {
            return ((double) arr[arr.length/2] + (double) arr[arr.length/2 - 1]) / 2;
        } else {
            return arr[arr.length/2];
        }
    }
复制代码

测试代码

测试代码如下所示：

    public static void main(String[] args) {
        Number4 n = new Number4();
        int[] nums1 = {2, 3};
        int[] nums2 = {1, 4, 5, 7};
        double ret = n.findMedianSortedArrays(nums2, nums1);
        System.out.println("ret：" + ret);
    }
复制代码