题解 | #多数组中位数#

多数组中位数

http://www.nowcoder.com/practice/b6bb0bce88894108bfc23e9b7b012420

题意整理

给定两个升序的数组arr1和arr2。
求这两个数组合并后的下中位数。

方法一（归并）

1.解题思路

本题需要求两个有序数组合并后的下中位数，假设合并后数组的长度为 $m + n$ ，则下中位数刚好是新数组中第 $(m + n) / 2$ 小的数，令K等于 $(m + n) / 2$ ，则可以将问题转化为求新数组中恰好第K小的数。

执行K次循环，每次将较小的值赋值给res。
新建两个变量id1、id2，id1是arr1数组游标，id2是arr2数组游标。如果id1和id2都没有到末尾，将两者指向的值中较小的赋值给res，并后移游标。
如果id1到达末尾，则继续将arr2数组的值赋值给res。否则，将arr1数组的值赋值给res。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @return int整型
     */
    public int getUpMedian (int[] arr1, int[] arr2) {
        int m=arr1.length;
        int n=arr2.length;
        //用于记录结果
        int res=0;
        //id1是arr1数组游标，id2是arr2数组游标
        int id1=0,id2=0;
        
        int K=(m+n)/2;
        //循环K次，每次将较小的值赋值给res，最后res一定是第K小的数
        while(K-->0){
            //如果id1和id2都没有到末尾
            if(id1<m&&id2<n){
                //将两者中较小的赋值给res，并后移游标
                if(arr1[id1]<arr2[id2]){
                    res=arr1[id1++];
                }
                else{
                    res=arr2[id2++];
                }
            }
            //如果id1到达末尾，则继续将arr2数组的值赋值给res
            else if(id1==m){
                res=arr2[id2++];
            }
            //否则，将arr1数组的值赋值给res
            else{
                res=arr1[id1++];
            }
        }
        return res;    
    }
}

3.复杂度分析

时间复杂度：需要给res赋值K次，循环总共执行K次，而K为 $m + n$ 的一半，所以时间复杂度是 $O (m + n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（二分法）

1.解题思路

根据之前的分析，合并后第 $(m + n) / 2$ 小的元素即是所求下中位数。可以通过求枢纽值的方式逐步缩小可能第k小的元素的范围，同时k也会随着动态变化。核心思想是求arr1的枢纽值位置，记为pivotKey1（保证arr1中pivotKey1左边的数都小于等于当前，并且数量不超过 $k / 2 - 1$ ），求arr2的枢纽值位置，记为pivotKey2（保证arr2中pivotKey2左边的数都小于等于当前，并且数量不超过 $k / 2 - 1$ ）。假设pivot为nums1[pivotKey1]、nums2[pivotKey2]中的较小者，则pivot最大也只能是k-1小，所以小于pivot的数都可以排除掉。

定义arr1和arr2数组的起始位置，分别记为l1和l2。
如果l1达到边界，说明nums1数组里的元素全部排除掉，取当前的nums2数组第k小即可。如果l2达到边界，说明nums2数组里的元素全部排除掉，取当前的nums1数组第k小即可
如果k变为1，说明第k小不是num1s数组当前左边界元素，就是nums2数组当前左边界元素，取两者中的较小者。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @return int整型
     */
    public int getUpMedian (int[] arr1, int[] arr2) {
        int m=arr1.length,n=arr2.length;
        //合并后，中位数的索引位置
        int k=(m+n)/2;
        return getKthMin(arr1,arr2,k);
    }
    
    public int getKthMin(int[] nums1, int[] nums2, int k) {
        //两个数组的起始位置
        int l1=0,l2=0;
        //数组长度
        int m=nums1.length,n=nums2.length;
        while(true){
            //如果l1达到边界，说明nums1数组里的元素全部排除掉，取当前的nums2数组第k小即可
            if(l1==m){
                return nums2[l2+k-1];
            }
            //如果l2达到边界，说明nums2数组里的元素全部排除掉，取当前的nums1数组第k小即可
            if(l2==n){
                return nums1[l1+k-1];
            }
            //如果k变为1，说明第k小不是num1s数组当前左边界元素，就是nums2数组当前左边界元素
            if(k==1){
                return Math.min(nums1[l1],nums2[l2]);
            }
            //保证nums1中pivotKey1左边的数都小于等于当前，并且数量不超过k/2-1
            int pivotKey1=Math.min(l1+k/2-1,m-1);
            //保证nums2中pivotKey2左边的数都小于等于当前，并且数量不超过k/2-1
            int pivotKey2=Math.min(l2+k/2-1,n-1);
            /*假设pivot为nums1[pivotKey1]、nums2[pivotKey2]中的较小者，则pivot
            最大也只能是k-1小，所以小于pivot的数都可以排除掉 */
            if(nums1[pivotKey1]<=nums2[pivotKey2]){
                //pivot为pivotKey1的情况
                k-=pivotKey1-l1+1;
                l1=pivotKey1+1;
            }
            else{
                //pivot为pivotKey2的情况
                k-=pivotKey2-l2+1;
                l2=pivotKey2+1;
            }
        }
    }
}