本文共 4260 字，大约阅读时间需要 14 分钟。

题目描述

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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

来源：力扣（LeetCode）

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

C++

class Solution {
   public:    double findMedianSortedArrays(vector
   
    & nums1, vector
    
     & nums2) {
           //Log(n)：每操作一次，需要处理的规模就小一半。        /*        如果要设计一个算法，让其具有log(n)的时间复杂度，从正面思考是困难的。        我们不妨想一想有没有什么操作是每操作一次，需要处理的规模就小一半的。        特别经典的例子就是二分搜索。        每次取中位数，在其左或其右继续搜索目标值。        其本质就是每搜索一次，就把待搜索的数据量减小了一半。        在这之上还有二分搜索树，log(n)其实就是二分搜索树的高度.        log(n)指的是 该算法随着输入规模翻倍，操作次数只增加一。        */       //对时间复杂度的要求有 \loglog，通常都需要用到二分查找，这道题也可以通过二分查找实现。       int sumlength=nums1.size()+nums2.size();       if(sumlength %2 ==1){
              return getKsamall(nums1,nums2,(sumlength+1)/2);       }else{
               return (getKsamall(nums1,nums2,sumlength/2)+getKsamall(nums1,nums2,sumlength/2+1))/2.0;       }           }    int getKsamall(vector
     
      & nums1, vector
      
       & nums2,int k){
           int len1=nums1.size();        int len2=nums2.size();        int index1=0;  //两个数组分别一个从0开始的指针，比较两个指针所指值,        int index2=0;  //每次数值较小的那个指针向后移动。        while(true){
               if(index1==len1){
       //数组1排除尽了                return nums2[index2+k-1];              }            if(index2==len2){
                   return nums1[index1+k-1];  //数组2排除尽了            }            if(k==1){
                   return min(nums1[index1],nums2[index2]);  //K==1时，就要结束了            }            //其他正常情况：            int newindex1=min(index1+k/2-1,len1-1);            int  newindex2=min(index2+k/2-1,len2-1);            int pivot1=nums1[newindex1];            int pivot2=nums2[newindex2];            if(pivot1<=pivot2){
                   k -= newindex1 - index1 + 1;                index1 = newindex1 + 1;            }else{
                   k -= newindex2 - index2 + 1;                index2 = newindex2 + 1;            }                    }    }};
      
     
    
   

java

class Solution {
       public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           int len1=nums1.length;        int len2=nums2.length;        int  sum_len=len1+len2;        if(sum_len%2==1){
               int midindex=sum_len/2;            double median=getKthElement(nums1,nums2,midindex+1);            return median;        }else{
               int midindex1=sum_len/2-1;            int midindex2=sum_len/2;            double median=(getKthElement(nums1,nums2,midindex1+1)+getKthElement(nums1,nums2,midindex2+1))/2.0;            return median;        }    }    public int getKthElement(int [] nums1, int [] nums2,int k){
            /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较         * 这里的 "/" 表示整除         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个         * 这样 pivot 本身最大也只能是第 k-1 小的元素         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数         */        int len1=nums1.length;        int len2=nums2.length;        int index1=0;        int index2=0;        int kthElement=0;        while(true){
               //边界情况            if(index1==len1){
                   return nums2[index2+k-1];            }            if(index2==len2){
                   return nums1[index1+k-1];            }            if(k==1){
                   return Math.min(nums1[index1],nums2[index2]);            }            //正常情况            int half=k/2;            int newindex1=Math.min(index1+half,len1)-1;            int newindex2=Math.min(index2+half,len2)-1;             int pivot1=nums1[newindex1];             int pivot2=nums2[newindex2];             if(pivot1<=pivot2){
                    k-= (newindex1-index1+1);                 index1=newindex1+1;             }else{
                    k-=(newindex2-index2+1);                 index2=newindex2+1;             }             }     }    }