多数组中位数

题目主要信息

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

注意：下中位数指在两个数组的数个数在偶数时取更小的

方法一：合并+遍历

具体方法

可以将两个数组中的结果按照升序的顺序存入到List中，然后直接输出最中间的数字即可。

arr1的长度为len1，arr2的长度为len2；索引i标记arr1，j标记arr2。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @return int整型
     */
    public int getUpMedian (int[] arr1, int[] arr2) {
        // write code here
        List<Integer> temp = new ArrayList<>();
        int len1 = arr1.length,len2 = arr2.length;
        int i = 0,j = 0;
      // 两者都满足索引大小
        while(i<len1 && j < len2){
          // arr1小
            if(arr1[i]<arr2[j]){
                temp.add(arr1[i]);
                i++;
            }else{
                temp.add(arr2[j]);
                j++;
            }
        }
      // 如果i没遍历完
        while(i<len1){
            temp.add(arr1[i]);
            i++;
        }
      // 如果j没遍历完
        while(j<len2){
            temp.add(arr2[j]);
            j++;
        }
      // 取中间的索引
        int mid = (len1+len2)/2;
      // 如果是偶数
        if((len1+len2) %2 == 0){
            mid = (len1+len2)/2;
          // 返回最小的索引
            return temp.get(mid-1);
        }
          // 如果是奇数
        else{
            mid = (len1+len2+1)/2;
            return temp.get(mid);
        }
    }
}

复杂度分析

• 时间复杂度：$O(m+n)O(m+n)$,需要遍历两个数组
• 空间复杂度：$O(m+n)O(m+n)$,存储两个数组的元素的temp。

方法二：双指针优化空间复杂度

具体方法

使用双指针i和j，i标记arr1的索引位置，j标记arr2的索引位置。

根据两个数组的大小求出k，执行k次循环，在每一轮将较小的赋值结果。

跟方法一类似，这里不用temp数组了，而是用一个临时遍历result。

代码实现

import java.util.*;

public class Solution {
    public int getUpMedian(int[] arr1, int[] arr2) {
        //k为中位数在两个数组中所处的位置，从1开始计数，由升序排序的第几个数

        int len1 = arr1.length,len2 = arr2.length;
        int k = (arr1.length + arr2.length ) / 2;
                //循环K次，每次将较小的值赋值给result，最后result一定是第K小的数
        int result = 0;
        int i =0,j = 0;
        while(k-->0){
            //如果i和j都没有到末尾
            if(i < len1 && j<len2){
                //将两者中较小的赋值给res，并后移游标
                if(arr1[i]<arr2[j]){
                    result = arr1[i++];
                }
                else{
                    result = arr2[j++];
                }
            }
            //如果i到达末尾，则继续将arr2数组的值赋值给res
            else if(i == len1){
                result = arr2[j++];
            }
            //否则，将arr1数组的值赋值给res
            else{
                result = arr1[i++];
            }
        }

        return result;
    }
}

复杂度分析

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

本题还可以优化时间复杂度。

中位数的划分作用，就很接近答案了。

首先，在任意位置 i将 A 划分成两个部分：

       left_A            |          right_A
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

由于A 中有 m 个元素， 所以有 m+1 种划分的方法i∈[0,m]）。

$len(lef{t}_A)=i,len(righ{t}_A)=m\mathrm{-}ilen(left\_A)=i,len(right\_A)=m-i$.

注意：$\mathrm{当}i=0\mathrm{时}\mathrm{，}lef{t}_A\mathrm{为}\mathrm{空}\mathrm{集}\mathrm{，}\mathrm{而}\mathrm{当}i=m\mathrm{时},righ{t}_A\mathrm{为}\mathrm{空}\mathrm{集}\mathrm{。}当\; i=0\; 时，left\_A\; 为空集，\; 而当\; i=m\; 时,right\_A\; 为空集。$

采用同样的方式，在任意位置 j 将B 划分成两个部分：

       left_B            |          right_B
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

将 $lef{t}_A\mathrm{和}lef{t}_{B}left\_A\; 和left\_B$放入一个集合，并将$righ{t}_{A}right\_A$和$righ{t}_{B}right\_B$放入另一个集合。 再把这两个新的集合分别命名为$lef{t}_{p}art\mathrm{和}righ{t}_{p}artleft\_part\; 和right\_part$：

      left_part          |         right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

当 A 和 B 的总长度是偶数时，如果可以确认：

• $len(lef{t}_{p}art)=len(righ{t}_{p}art)len(left\_part)=len(right\_part)$
• $max(lef{t}_{p}art)\le min(righ{t}_{p}art)max(left\_part)\le min(right\_part)$

那么，{A,B} 中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值：

• $median=max(lef{t}_{p}art)+min(righ{t}_{p}art)\mathrm{/}2median=\; max(left\_part)+min(right\_part)/2$

当 A 和B 的总长度是奇数时，如果可以确认：

• $len(lef{t}_{p}art)=len(righ{t}_{p}art)+1len(left\_part)=len(right\_part)+1$
• $max(lef{t}_{p}art)\le min(righ{t}_{p}art)max(left\_part)\le min(right\_part)$

那么，{A,B} 中的所有元素已经被划分为两个部分，前一部分比后一部分多一个元素，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值：

• $median=max(lef{t}_{p}art)median=max(left\_part)$

第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。第二个条件对于总长度是偶数和奇数的情况是一样的。

要确保这两个条件，只需要保证：

• $i+j=m\mathrm{-}i+n\mathrm{-}ji+j=m-i+n-j$（当 m+n 为偶数）或$i+j=m\mathrm{-}i+n\mathrm{-}j+1i+j=m-i+n-j+1$（当 m+n 为奇数）。等号左侧为前一部分的元素个数，等号右侧为后一部分的元素个数。将 i和 j全部移到等号左侧，我们就可以得到 $i+j=m+n+1\mathrm{/}2i+j=\; m+n+1/2$。这里的分数结果只保留整数部分。

• $0\le j\le n0\le j\le n$。如果我们规定 A 的长度小于等于B 的长度，即 $m\le nm\le n$。这样对于任意的 $i\in [0,m]i\in [0,m]$，都有$j=m+n+1\mathrm{/}2\mathrm{-}i\in [0,n]j=\; m+n+1/2-i\in [0,n]$，那么我们在 $[0,m][0,\; m]$的范围内枚举 i并得到 j，就不需要额外的性质了。

  • 如果A 的长度较大，那么我们只要交换 A 和B 即可。

  • 如果m>n ，那么得出的 jj 有可能是负数。

• $B[j\mathrm{-}1]\le A[i]\mathrm{以}\mathrm{及}A[i\mathrm{-}1]\le B[j]B[j-1]\le A[i]\; 以及\; A[i-1]\le B[j]$，即前一部分的最大值小于等于后一部分的最小值。

为了简化分析，假设 $A[i\mathrm{-}1],B[j\mathrm{-}1],A[i],B[j]A[i-1],B[j-1],A[i],B[j]$ 总是存在。对于$i=0\mathrm{、}i=m\mathrm{、}j=0\mathrm{、}j=ni=0、i=m、j=0、j=n$这样的临界条件，我们只需要规定$A[\mathrm{-}1]=B[\mathrm{-}1]=\mathrm{-}\mathrm{\infty }A[-1]=B[-1]=-\infty$，$A[m]=B[n]=\mathrm{\infty }A[m]=B[n]=\infty$ 即可。这也是比较直观的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。

所以我们需要做的是：在 $[0,m]\mathrm{中}\mathrm{找}\mathrm{到}i\mathrm{，}\mathrm{使}\mathrm{得}\mathrm{：}B[j\mathrm{-}1]\le A[i]\mathrm{且}A[i\mathrm{-}1]\le B[j]\mathrm{，}\mathrm{其}\mathrm{中}j=m+n+1\mathrm{/}2\mathrm{-}i[0,\; m]中找到\; i，使得：B[j-1]\le A[i]\; 且A[i-1]\le B[j]，其中\; j=\; m+n+1/2\; -i$

我们证明它等价于：

在 $[0,m][0,\; m]$中找到最大的 i，使得：$A[i\mathrm{-}1]\le B[j]\mathrm{，}\mathrm{其}\mathrm{中}j=m+n+1\mathrm{/}2-iA[i-1]\le B[j]，其中j=\; m+n+1/2-i$

这是因为：

• 当 $i\mathrm{从}0\sim mi\; 从0\sim m$ 递增时，A[i−1] 递增，B[j] 递减，所以一定存在一个最大的 i 满足$A[i\mathrm{-}1]\le B[j]A[i-1]\le B[j]$；
• 如果 i是最大的，那么说明 $i+1i+1$ 不满足。将 $i+1i+1$ 带入可以得到 $A[i]>B[j\mathrm{-}1]A[i]>B[j-1]$，也就是 ，就和我们进行等价变换前 i的性质一致了（甚至还要更强）。

因此我们可以对 $ii$在 $[0,m][0,\; m]$的区间上进行二分搜索，找到最大的满足 $A[i\mathrm{-}1]\le B[j]A[i-1]\le B[j]$ 的 i 值，就得到了划分的方法。此时，划分前一部分元素中的最大值，以及划分后一部分元素中的最小值，才可能作为就是这两个数组的中位数。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @return int整型
     */
    public int getUpMedian (int[] arr1, int[] arr2) {
        // write code here
        if (arr1.length > arr2.length) {
            return getUpMedian(arr2, arr1);
        }

        int m = arr1.length;
        int n = arr2.length;
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : arr1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : arr1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : arr2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : arr2[j]);

            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ?  median1 : (median1 + median2) / 2;
    }
}

复杂度分析

• 时间复杂度：时间复杂度是$O(logmin(m,n)))O(logmin(m,n)))$,查找的区间是 $[0,m][0,\; m]$，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为$O(logm)O(logm)$。由于我们可能需要交换 $nums1\mathrm{和}nums2\mathrm{使}\mathrm{得}m\le nnums1\; 和nums2使得m\le n$
• 空间复杂度：$O(1)O(1)$。