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

题目

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

链接：https://leetcode.cn/problems/median-of-two-sorted-arrays

我的解答

双指针直接拼接成一个新的数组，然后取中位数。需要额外 n+m 的空间，但只需要各自遍历一遍。
另外有一个问题需要注意，新生成的数组nums 和 nums1``,nums2都需要各自的下标记录。

还有一个技巧需要注意，不论总个数是奇数还是偶数，计算中位数的方式(我试出来的)

1 2	int right = nums.length/2; int left = (nums.length+1)/2-1;

代码

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int [] nums = new int[length];

    int i = 0, a = 0,b = 0;
    for (; a<nums1.length && b<nums2.length; ){

        if(nums1[a] < nums2[b]){
            nums[i] = nums1[a];
            a++;
        }else{
            nums[i] = nums2[b];
            b++;
        }
        i++;
    }
    while (a<nums1.length){
        nums[i++] = nums1[a];
        a++;
    }
    while (b<nums2.length){
        nums[i++] = nums2[b];
        b++;
    }

    int right = nums.length/2;
    int left = (nums.length+1)/2-1;

    return (double)(nums[left]+nums[right])/2;
}

出问题了，算法的时间复杂度应该为 O(log (m+n)) 。上面算法时间复杂度是 **O(m+n)**，不符合要求。
目前没思路。先跳过了。

参考答案

时间复杂度需要O(log(m+n) 必然是用二分法，题目要求是求中位数，其实就是求第 k小的数的一种特殊情况。
一般都是一个个的遍历去掉不可能是中位数的逻辑，但是因为数组是有序的，完全可以一半一半的排除。
所以，假设我们要找到第k小数，我们可以每次循环排除掉k/2个数。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
    if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
    if (len1 == 0) return nums2[start2 + k - 1];

    if (k == 1) return Math.min(nums1[start1], nums2[start2]);

    int i = start1 + Math.min(len1, k / 2) - 1;
    int j = start2 + Math.min(len2, k / 2) - 1;

    if (nums1[i] > nums2[j]) {
        return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    }
    else {
        return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}

https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/