一、题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

二、解题

中位数：是按顺序排列的一组数据中居于中间位置的数，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分

这道题真的好难啊，毕竟算法的时间复杂度要求在那呢，不是说给出答案就好了，还需要最优解。
这边我参考了leetcode的一位大神的截图思路，再加上我的理解输出一丢丢哈

三、源码

    public static void main(String[] args) {
        int nums1[] = {2, 7, 11, 15};
        int nums2[] = {3, 7, 8, 14, 45};
        double result = findMedianSortedArrays(nums1, nums2);
        System.out.println("result:" + result);
    }


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;//拿到数组1的长度
        int m = nums2.length;//拿到数组2的长度
        int odd = (n + m + 1) / 2;//数组之和为奇数时，中位数的角标
        int even = (n + m + 2) / 2;//数组之和为偶数时，中位数的角标
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getNth(nums1, 0, n - 1, nums2, 0, m - 1, odd) + getNth(nums1, 0, n - 1, nums2, 0, m - 1, even)) *0.5;
    }

    /**
     * 获取第n小的数，该数为所求中位数
     *
     * @param nums1  数组1
     * @param start1 开始的角标
     * @param end1   结束的角标
     * @param nums2  数组2
     * @param start2 开始的角标
     * @param end2   结束的角标
     * @param n
     * @return
     */
    private static int getNth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int n) {
        int len1 = end1 - start1 + 1;//拿到需要比较的数组1长度
        int len2 = end2 - start2 + 1;//拿到需要比较的数组2长度
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) return getNth(nums2, start2, end2, nums1, start1, end1, n);
        //当数组1里面没有我们要找的数时，直接放回数组2中第N小的值
        if (len1 == 0) return nums2[start2 + n - 1];
        //当n等于1时，说明下一个数就是中位数了，这时候只需要比较两个数组剩余的数中最小的值
        if (n == 1) return Math.min(nums1[start1], nums2[start2]);
        //计算下一个需要比较的角标，
        int i = start1 + Math.min(len1, n / 2) - 1;
        int j = start2 + Math.min(len2, n / 2) - 1;
        //判断数组1中第i个和数组2中第j个大小。
        //如果数组1中的第i个数比较大，说明数组2中j之前的数都不是我们要找的中位数，可以将数组2查找的角标移到j+1在重新比较。
        if (nums1[i] > nums2[j]) {
            //这里没有找到第n个小的，需要递归，n=n-去掉的数-1。
            return getNth(nums1, start1, end1, nums2, j + 1, end2, n - (j - start2 + 1));
        }
        //如果数组2中的第j个数比较大也是如此。
        else {
            return getNth(nums1, i + 1, end1, nums2, start2, end2, n - (i - start1 + 1));
        }
    }
}

四、附上github

https://github.com/maryyMa/LeetCodeTest/commit/86bef193c607f6c2ed553118af74d1eb61550852