题目描述

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

样例

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

算法1

(暴力枚举) $O(n)$

开一个新数组存放合并排序后的结果，当然可以做小优化：中位数角标为mid,只排前mid个数字

时间复杂度 $O(n)$

Java 代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len=nums1.length+nums2.length;
        int[] res=new int[len];
        int mid=len>>1;
        int idx=0,l=0,r=0;
        while(idx<=mid){
            if(l<nums1.length&&r<nums2.length){
                if(nums1[l]>nums2[r]){
                    res[idx++]=nums2[r++];
                }else{
                    res[idx++]=nums1[l++];
                }
            }else if(l>=nums1.length){
                res[idx++]=nums2[r++];
            }else if(r>=nums2.length){
                res[idx++]=nums1[l++];
            }
        }
        if(len%2==0){
            return (res[mid-1]+res[mid])/2.0;
        }else{
            return res[mid]/1.0;
        }
    }
}

算法2

二分法

假设中位数为第K，两个数组平分该值，分别找出并比较各数组中第k/2个值的大小，由于数组的都是有序的，第k/2个小的那个数组的前k/2（含）不会参与到中位数的确定，只需要从k-k/2中选，一直将k值减为1即可

时间复杂度 $O(log(m+n))$

Java 代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n=nums1.length+nums2.length;
        if(n%2==0){
            int r1=findMid(nums1,nums2,0,0,n>>1);
            int r2=findMid(nums1,nums2,0,0,(n>>1)+1);
            return (r1+r2)/2.0;
        }else{
            return findMid(nums1,nums2,0,0,(n+1)>>1)/1.0;
        }
    }
    private int findMid(int[] nums1, int[] nums2,int start1,int start2,int k){
        if(nums1.length-start1>nums2.length-start2){
            return findMid(nums2,nums1,start2,start1,k);
        }
        if(nums1.length==start1){
            return nums2[start2+k-1];
        }
        if(k==1){
            return Math.min(nums1[start1],nums2[start2]);
        }
        int t=k>>1;
        int ss1=Math.min(nums1.length,start1+t);
        int ss2=start2+(k-t);
        if(nums1[ss1-1]>nums2[ss2-1]){
            return findMid(nums1,nums2,start1,ss2,k-(ss2-start2));
        }else{
            return findMid(nums1,nums2,ss1,start2,k-(ss1-start1));
        }
    }
}