给定两个大小分别为 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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？（我表示没有做到）

class Test4 {
    /**
     * 直接用归并排序来做排序，然后取中位数即可
     * 执行用时：78 ms, 在所有 Java 提交中击败了5.14%的用户 内存消耗：39.8 MB, 在所有 Java 提交中击败了33.73%的用户
     * 扎心，看来排序不靠谱O(N*lgN)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 设置中位数的值
        double result = 0d;
        if (nums1.length == 0 && nums2.length == 0) {
            return result;
        }
        // 对左边进行归并排序
        mergeSort(nums1, 0, nums1.length - 1);
        System.out.println("nums1排序之后：");
        for (int i = 0; i < nums1.length; i++) {
            System.out.print(nums1[i] + " ");
        }
        // 对右边进行归并排序
        mergeSort(nums2, 0, nums2.length - 1);
        System.out.println("nums2排序之后：");
        for (int i = 0; i < nums2.length; i++) {
            System.out.print(nums2[i] + " ");
        }
        // 对两边进行合并
        int[] nums = new int[nums1.length + nums2.length];
        mergeNums1Nums2(nums, nums1, nums2);
        System.out.println("nums排序之后：");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        // 取中位数
        int mid = nums.length / 2;
        if (nums.length % 2 == 0) {
            // 表明是偶数，取中间的和上一个相加
            result = (nums[mid] + nums[mid - 1]) / 2d;
        } else {
            result = nums[mid];
        }
        System.out.println("中位数：" + result);
        return result;
    }
    private void mergeNums1Nums2(int[] nums, int[] nums1, int[] nums2) {
        int nums1_left = 0;
        int nums1_right = nums1.length - 1;
        int nums2_left = 0;
        int nums2_right = nums2.length - 1;
        int now = 0;
        while (nums1_left <= nums1_right && nums2_left <= nums2_right) {
            // 从两个数组中选取较小的数放入中间数组
            if (nums1[nums1_left] <= nums2[nums2_left]) {
                nums[now] = nums1[nums1_left];
                nums1_left++;
            } else {
                nums[now] = nums2[nums2_left];
                nums2_left++;
            }
            now++;
        }
        // 将剩余的部分放入中间数组
        while (nums1_left <= nums1_right) {
            nums[now] = nums1[nums1_left];
            nums1_left++;
            now++;
        }
        while (nums2_left <= nums2_right) {
            nums[now] = nums2[nums2_left];
            nums2_left++;
            now++;
        }
    }
    private void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            // 对左边进行递归
            mergeSort(a, left, middle);
            // 对右边进行递归
            mergeSort(a, middle + 1, right);
            // 合并
            merge(a, left, middle, right);
        }
    }
    private void merge(int[] a, int left, int middle, int right) {
        int[] tmpArr = new int[a.length];
        int mid = middle + 1; // 右边的起始位置
        int tmp = left;
        int third = left;
        while (left <= middle && mid <= right) {
            // 从两个数组中选取较小的数放入中间数组
            if (a[left] <= a[mid]) {
                tmpArr[third++] = a[left++];
            } else {
                tmpArr[third++] = a[mid++];
            }
        }
        // 将剩余的部分放入中间数组
        while (left <= middle) {
            tmpArr[third++] = a[left++];
        }
        while (mid <= right) {
            tmpArr[third++] = a[mid++];
        }
        // 将中间数组复制回原数组
        while (tmp <= right) {
            a[tmp] = tmpArr[tmp++];
        }
    }
    public static void main(String[] args) {
        int[] num1 = { 1, 2 };
        int[] num2 = { 3, 4 };
        new Test4().findMedianSortedArrays(num1, num2);
    }
}

丢人，超过的人太少了！

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays