[力扣_4] 寻找两个正序数组的中位数

题目入口:点击进入

相关算法:

  • 二分查找——时间复杂度:O(min*logn),空间复杂度O(1)达到题目要求
  • 归并排序——时间复杂度:O(m+n/2),空间复杂度O(m+n/2)未达到题目要求
  • 分而治之——时间复杂度:O(log min(m,n)),空间复杂度O(1)达到题目要求

此题为困难题,难就难在O(logn)的时间限制上,归并排序很好理解,但是达不到题目的要求。

此题运用了中位数的特性结合二分查找达到O(logn)的时间复杂度。

分而治之(划分数组)

分治的思想是把一个大的问题分开来处理,正好对应了中位数的特性,并且在正序排列数组中,能用到

思路与算法

为了使用划分的方法解决这个问题,需要理解中位数的作用是什么,在统计中,中位数被用来:将一个集合划分为两个长度相等的子集,其中一个自己中的元素总是大于另一个子集中的元素

如理解可中位数的划分作用,就很接近答案了。

我们可以让第一个数组一直大于第二个数组,在第一个数组上定位分割线的作用,然后不断的缩小区间。

我们知道,左边的集合要一直大于右边的集合,而且分割线两边的元素要实现交叉(大于||小于),并且为了结合奇偶的情况,我们让左边的元素比右边的元素多出一位,则在奇数情况下,分割线左边最大的元素值就为它的中位数

而在偶数的情况下,分割线右边最小的元素值加上分割线左边最大的元素值除二就为它的中位数。

当然,分割线划定的区间为:[0....i]&&[i....m],都为左开右闭区间,则i的值就为数组左半边的元素个数,又因为是有序数组:i-1得值就为数组左半边最大的元素,i的值就为右半边最小的元素

同理,在第二个数组中,拿j做指针,与上相同的道理,同时需要满足左半边的元素要近乎等于右半边的元素,这是可以计算出来的

我们将两数组的元素个数相加在一起,加一除以二就能得到左半边的元素个数,在此,左半边严格大于右半边的元素。

例如:

利用二分查找的特性,我们在数组A上确定分割线的位置,每次将搜索区间降低一半
i=4+1/2=2
j=6-2=4
注意下标
A={1,2 | 3,4}           mlen=4
B={6,7,8,9 | 10,11,12}  nlen=7
则元素个数总和为4+7=11,加1除2得到左半边的个数为6,也是数组合并后中位数的个数,我们一定要记住题目给出的特性:正序有序排列

那么此时 i 就指向3,指针 j 的个数就可以由左半边的总元素减去数组A已经提供给左半边的元素得到

  • 因为左半边一共需要6个元素,而 i 指针在A数组中已经给左半边提供了2个元素,则第二个数组还需要给左半边提供 4 个元素
  • 这个时候,左半边和右半边的数组元素个数达到要求,下面要看他们是否交叉(大于小于)

数组A在左半边最大的元素要小于数组B在右半边最小的元素,同理,数组B在左半边最小的元素要小于数组A在右半边最大的元素,显然,2<10,但是9>3

这个时候我们就可得知:

  • 数组A的分割线太靠左了,当时左半边没有符合要求的元素值,就可以将搜索区间缩小一半,为[3 4]

重复刚才的操作,取到3 4 的中心位置加一得到 4 如下所示

A={1,2,3 | 4}
b={6,7,8 |9,10,11,12}

同理,依旧不满足,则继续将区间缩小一般,左边界到 i 的位置来

A={1,2,3,4 |}
b={6,7 | 8,9,10,11,12}

这个时候左边界与右边界相遇了,则中位数不包括在第一个数组中,只包括在第二个数组中

  • 又因为两数组总和为奇数,返回左半边最大的元素,就是 7
  • 偶数就返回左半边最大的元素和右半边最小元素和/2就行

在最后得到的结果,只与数组A左半边最大和右半边最小和数组B左半边最大和右半边最小四个数有关,例如:

A={1,3 | 9,11}
b={6,7,8,9 | 10,11,12}

以上思路根据官方题解得到,官方题解有点难懂,点击观看官方题解

官方题解的视频和第二个方法就是以下代码所展示的方法

代码如下:

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){

    int m=nums1Size,n=nums2Size;
    //让一个数组永远为最小
    if(nums1Size>nums2Size){
        int *temp;
        temp=nums1;
        nums1=nums2;
        nums2=temp;

        int tempSize;
        tempSize=m;
        m=n;
        n=tempSize;
}

    int Sumsize=m+n;
    int Median=(Sumsize+1)/2;
    
    int left=0;
    int right=m;

    int i,j;
    while(left<right)
    {
      i=left+((right-left+1)/2);//i初值为num1的中位数
      j=Median-i;
      if(nums1[i-1]>nums2[j])
      {
          right=i-1;
      }
      else
      {
          left=i;
      }
    }

    i=left;
    j=Median-i;

    //划定边界
    int nums1MaxLeft=i==0?-2147483647:nums1[i-1];
    int nums1MInRight=i==m?2147483647:nums1[i];
    int nums2MaxLeft=j==0?-2147483647:nums2[j-1];
    int nums2MInRight=j==n?2147483647:nums2[j];

    if(Sumsize%2==1)
    {
        return nums2MaxLeft>nums1MaxLeft?nums2MaxLeft:nums1MaxLeft;
    }
    else{
        int a=nums2MaxLeft>nums1MaxLeft?nums2MaxLeft:nums1MaxLeft;
        int b=nums2MInRight<nums1MInRight?nums2MInRight:nums1MInRight;
        return (double)(a+b)/2;
    }
}

二分查找(第K小数法)

我们一次遍历就相当于去掉不可能是中位数的一个值,也就是一个一个排除。由于数列是有序的,其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。看下边一个例子。

假设我们要找第 7 小的数字。

img

我们比较两个数组的第 k/2 个数字,如果 k 是奇数,向下取整。也就是比较第 33 个数字,上边数组中的 4 和下边数组中的 3,如果哪个小,就表明该数组的前 k/2 个数字都不是第 k 小数字,所以可以排除。也就是 1,2,3 这三个数字不可能是第 7 小的数字,我们可以把它排除掉。将 1,3,4,9 和 4,5,6,7,8,9,10两个数组作为新的数组进行比较。

更一般的情况 A[1] ,A[2] ,A[3],A[k/2] … ,B[1],B[2],B[3],B[k/2] … ,如果 A[k/2]<B[k/2] ,那么A[1],A[2],A[3],A[k/2]都不可能是第 k 小的数字。

A 数组中比 A[k/2] 小的数有 k/2-1 个,B 数组中,B[k/2] 比 A[k/2] 小,假设 B[k/2] 前边的数字都比 A[k/2] 小,也只有 k/2-1 个,所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个,所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了,所以可以把它们排除。

橙色的部分表示已经去掉的数字。

img

由于我们已经排除掉了 3 个数字,就是这 3 个数字一定在最前边,所以在两个新数组中,我们只需要找第 7 - 3 = 4 小的数字就可以了,也就是 k = 4。此时两个数组,比较第 2 个数字,3 < 5,所以我们可以把小的那个数组中的 1 ,3 排除掉了。

img

我们又排除掉 2 个数字,所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数,4 == 4,怎么办呢?由于两个数相等,所以我们无论去掉哪个数组中的都行,因为去掉 1 个总会保留 1 个的,所以没有影响。为了统一,我们就假设 4 > 4 吧,所以此时将下边的 4 去掉。

img

由于又去掉 1 个数字,此时我们要找第 1 小的数字,所以只需判断两个数组中第一个数字哪个小就可以了,也就是 4。

所以第 7 小的数字是 4。

我们每次都是取 k/2 的数进行比较,有时候可能会遇到数组长度小于 k/2的时候。如果遇到此情况,直接将问题规模缩小,删除较长数组中的k/2个元素,因为第一个数组不满足另外k/2个元素的条件,左半边没满,所以不管怎么样,较长数组中的前k/2个元素都不可能是第k小数!!!(两数组都为正序)

因为不管怎么样,如果存在第k小数的话,第一数组必须要满足存在k/2-1个元素,这样两边删除和存留的数加在一起才能得到第k小数。

代码如下所示:这递归很好理解,难理解的主要是在边界的处理上

int GetKth(int *nums1,int i,int *nums2,int j,int k,int nums1Size,int nums2Size){
    if(i>=nums1Size)
    {
        return nums2[j+k-1];//第一个数组跑完
    }
    if(j>=nums2Size)
    {
        return nums1[i+k-1];//第二个数组跑完
    }
    if(k==1)
    {
        return nums1[i]<nums2[j]?nums1[i]:nums2[j];//找到第k小数
    }
    int med1=(i+k/2-1)<nums1Size?nums1[i+k/2-1]:25600000;//提取这次比较的数
    int med2=(j+k/2-1)<nums2Size?nums2[j+k/2-1]:25600000;//如果有一方达到边界则让它赋最大值
    if(med1<med2)//比较较小值,模拟删除的数组
    {
        return GetKth(nums1,i+k/2,nums2,j,k-k/2,nums1Size,nums2Size);
    }
   return GetKth(nums1,i,nums2,j+k/2,k-k/2,nums1Size,nums2Size);
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){

int Sumsize=nums1Size+nums2Size;
int left=(Sumsize+1)/2;
int right=(Sumsize+2)/2;
 return (GetKth(nums1, 0, nums2, 0, left,nums1Size,nums2Size) + GetKth(nums1, 0, nums2, 0, right,nums1Size,nums2Size)) / 2.0;
}

归并排序

这种方法是最简单也是最常用的,时间复杂度取决于两数组的长度,在本题中可以优化到O(m+n/2),因为中位数在中间,只需要找到第m+n/2+1个就可以了。

使用双指针,按正序存放到一个新的数组中,循环次数是(m+n/2)+1,如果是奇数返回归并好后数组中倒数第二个,如果是偶数返回倒数第二和第一和除以二。

代码如下:

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int total=(nums1Size+nums2Size)/2+1;
    int temp[total];
    int i=0,j=0,p=0;
    while(i<nums1Size&&j<nums2Size&&p<total)
    {
       if(nums1[i]<nums2[j])
       {
           temp[p]=nums1[i];
           ++i;
           ++p;
       }
       else
       {
           temp[p]=nums2[j];
           ++j;
           ++p;
       }
    }
    while(p<total&&i<nums1Size){
        temp[p]=nums1[i];
        p++;
        i++;
    }
    while(p<total&&j<nums2Size){
        temp[p]=nums2[j];
        p++;
        j++;
    }

    if((nums2Size+nums1Size)%2==1)
    {
        return temp[total-1];
    }
    else{
        return (double)(temp[total-1]+temp[total-2])/2;
    }

}

我一直搞不懂LeetCode的判别功能...归并的成绩惊人...:

img

本文链接:

https://nullcode.fun/49.html
1 + 5 =
快来做第一个评论的人吧~