题解 | #两个升序数组的中位数#

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型ArrayList
     * @param nums2 int整型ArrayList
     * @return double浮点型
     */
    public double Median(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
        ArrayList<Integer> merged = new ArrayList<>();
        int n = nums1.size();
        int m = nums2.size();
        int i = 0, j = 0;

        while (i < n && j < m) {
            if (nums1.get(i) < nums2.get(j)) {
                merged.add(nums1.get(i));
                i++;
            } else {
                merged.add(nums2.get(j));
                j++;
            }
        }

        while (i < n) {
            merged.add(nums1.get(i));
            i++;
        }

        while (j < m) {
            merged.add(nums2.get(j));
            j++;
        }

        int length = merged.size();
        if (length % 2 == 0) {
            int mid = length / 2;
            return (merged.get(mid - 1) + merged.get(mid)) / 2.0;
        } else {
            return merged.get(length / 2);
        }
    }
}

题目描述：给定两个长度分别为 n 和 m 的升序数组，要求找到这两个数组中全部元素的中位数。

解题思路：要找到两个升序数组的中位数，可以使用合并排序的方法。首先，将两个数组合并成一个新的升序数组。然后，根据合并后数组的长度来确定中位数的位置，如果长度为奇数，中位数就是合并后数组中间位置的元素；如果长度为偶数，中位数是合并后数组中间两个位置元素的平均值。

具体步骤：

1. 创建一个新的数组，用于存储合并后的数组元素。
2. 使用双指针的方法，初始化两个指针分别指向两个数组的开头。
3. 比较指针位置的元素大小，将较小的元素放入新的数组中，并移动指向较小元素的指针。
4. 重复步骤3，直到遍历完两个数组的所有元素。
5. 如果合并后数组长度为奇数，返回中间位置的元素；如果长度为偶数，返回中间两个元素的平均值。

复杂度分析：

• 时间复杂度：合并排序需要遍历两个数组的所有元素，所以时间复杂度为 O(n + m)。
• 空间复杂度：创建了一个新的数组来存储合并后的数组元素，所以空间复杂度为 O(n + m)。