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

题目描述

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

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

方法一:

合并两个数组，对新数组求中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m+n];
        //如果nums1 的长度为零则直接找出nums2的中位数
        if(m == 0){
            if(n % 2 == 0){
                return (nums2[n/2-1]+nums2[n/2])/2.0;
            }
            else{
                return nums2[n/2];
            }
        }
        //如果nums2的长度为零则直接找出nums1的中位数
        if(n == 0){
            if(m % 2 == 0){
                return (nums1[m/2-1]+nums2[m/2])/2.0;
            }
            else{
                return nums1[m/2];
            }
        }
        //count用于给新数组赋值
        int count = 0;
        //i , j分别用来记录nums1 和 nums2数组所遍历到的位置
        int i = 0, j = 0;
        //对整个新数组进行赋值
        while(count != (m+n)){
            //如果当前nums1遍历到了最后，则将nums2剩下的元素依次赋值给nums
            if(i == m){
                while(j != n){
                    nums[count++] = nums2[j++];
                }
                //赋值完后就退出循环
                break;
            }
            //如果当前nums2遍历到了最后，则将nums1剩下的元素依次赋值给nums
            if(j == n){
                while(i != m){
                    nums[count++] = nums1[i++];
                }
                break;
            }
            //如果当前nums1 和nums2都还有元素，则进行两两对比
            if(nums1[i] < nums2[j]){
                nums[count++] = nums1[i++];
            }else{
                nums[count++] = nums2[j++];
            }
        }

        //退出循环后说明nums已经全部赋值完成，，此时就直接对新数组求中位数即可
        if(count % 2 == 0){
            return (nums[count/2-1] + nums[count/2]) / 2.0;
        }else{
            return nums[count/2];
        }
   }
}

方法二：

用 len 表示合并后数组的长度，如果是奇数，我们需要知道第 （len+1）/2 个数就可以了，如果遍历的话需要遍历 int(len/2 ) + 1 次。如果是偶数，我们需要知道第 len/2和 len/2+1 个数，也是需要遍历 len/2+1 次。所以遍历的话，奇数和偶数都是 len/2+1 次。

返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 left 和 right，right 保存当前循环的结果，在每次循环前将 right 的值赋给 left。这样在最后一次循环的时候，left 将得到 right 的值，也就是上一次循环的结果，接下来 right 更新为最后一次的结果。

循环中该怎么写，什么时候 A 数组后移，什么时候 B 数组后移。用 aStart 和 bStart 分别表示当前指向 A 数组和 B 数组的位置。如果 aStart 还没有到最后并且此时 A 位置的数字小于 B 位置的数组，那么就可以后移了。也就是aStart＜m && A[aStart]< B[bStart]。

但如果 B 数组此刻已经没有数字了，继续取数字 B[ bStart ]，则会越界，所以判断下 bStart 是否大于数组长度了，这样 || 后边的就不会执行了，也就不会导致错误了，所以增加为aStart＜m && (bStart >= n||A[aStart]<B[bStart])。

---

作者：windliang
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/8999/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
来源：力扣（LeetCode）

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int m = a.length;
        int n = b.length;
        int len = m + n;
        //left用来记录第 len/2 个数； right用来记录第 len/2 + 1 个数； 如果len为奇数则只需要遍历到第 len/2 +1 个数
        //如果len为偶数则取 len/2 和 len/2 + 1 的平均值
        int left = -1, right = -1;
        //aStart和bStart用来记录a和b数组的遍历位置
        int aStart = 0, bStart = 0;

        for(int i = 0; i <= len/2; i++){
            //每一次遍历完成后都需要将right的值赋给left,保证两个数都是同步更新
            left = right;
            //如果a没有遍历完， 并且  b已经遍历完或者 a和b都没遍历完但是a数组此时的值比b数组小 ===》
            //则将a数组正在遍历的值给最新的right赋值，并且继续遍历a数组的下一个数
            if(aStart < m && (bStart >= n || a[aStart] < b[bStart])){
                right = a[aStart++];
            }else{
                right = b[bStart++];
            }
            
        }

        if(len%2 == 0){
            return (left+right)/2.0;
        }else{
            return right;
        }
   }
}

方法三：

使用二分法，思路见下方链接。最终时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n）O(log(m+n）O(log(m+n）。

空间复杂度：虽然我们用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)O(1)O(1)。

作者：windliang
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/8999/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
来源：力扣（LeetCode）

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        //因为数组是从索引0开始的，因此我们在这里必须+1，即索引(k+1)的数，才是第k个数。
        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) {
        //因为索引和算数不同6-0=6，但是是有7个数的，因为end初始就是数组长度-1构成的。
        //最后len代表当前数组(也可能是经过递归排除后的数组)，符合当前条件的元素的个数
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        //就是如果len1长度小于len2，把getKth()中参数互换位置，即原来的len2就变成了len1，即len1，永远比len2小
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        //如果一个数组中没有了元素，那么即从剩余数组nums2的其实start2开始加k再-1.
        //因为k代表个数，而不是索引，那么从nums2后再找k个数，那个就是start2 + k-1索引处就行了。因为还包含nums2[start2]也是一个数。因为它在上次迭代时并没有被排除
        if (len1 == 0) return nums2[start2 + k - 1];

        //如果k=1，表明最接近中位数了，即两个数组中start索引处，谁的值小，中位数就是谁(start索引之前表示经过迭代已经被排出的不合格的元素，即数组没被抛弃的逻辑上的范围是nums[start]--->nums[end])。
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        //为了防止数组长度小于 k/2,每次比较都会从当前数组所生长度和k/2作比较，取其中的小的(如果取大的，数组就会越界)
        //然后素组如果len1小于k / 2，表示数组经过下一次遍历就会到末尾，然后后面就会在那个剩余的数组中寻找中位数
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        //如果nums1[i] > nums2[j]，表示nums2数组中包含j索引，之前的元素，逻辑上全部淘汰，即下次从J+1开始。
        //而k则变为k - (j - start2 + 1)，即减去逻辑上排出的元素的个数(要加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));
        }
    }