求两个有序数组中的中位数和第k小的元素

转x33g5p2x  于2022-02-07 转载在 其他  
字(8.9k)|赞(0)|评价(0)|浏览(455)

我们首先来看一下这一类题算法的原型：

对应牛客网链接：

https://www.nowcoder.com/practice/08588d568e164e0a9958b5d6a3c351f5?tpId=101&&tqId=33149&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D101%26type%3D101%26page%3D2

题目描述：

给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。

上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n个数

[要求]

时间复杂度为O(logN)，额外空间复杂度为O(1)

第一行一个整数N，表示数组大小。
接下来一行N个整数，表示arr1内的元素
再接下来一行N个整数，表示arr内的元素

输出一个整数表示答案

输入：

  1. 4
  2. 1 2 3 4
  3. 3 4 5 6

复制输出：

  1. 3

复制说明：

  1. 总共有8个数，上中位数是第4小的数，所以返回3。

输入：

  1. 3
  2. 0 1 2
  3. 3 4 5

复制输出：

  1. 2

复制说明：

  1. 总共有6个数，那么上中位数是第3小的数，所以返回2

解题思路：

我首先在长度为偶数的数组中两个数组中求上中位数。我们首先求A数组中的上中位数为b

在B数组中求其上中位数位b我们比较b和b'的大小如如下三种情况：

1.如果b==b'那么b的值就是上中位数这是为什么了呢？我们将b和b'看作一个整体就可以了明白了.

2.如果b大于b'.对于A和B数组合并之后的上中位数那么它一定是第四小的数此时我们可以排除掉一些不可能是上中位数的数字比如说A数组中的c和d这是因为c和d本来就大于a，b而b有大于b'当然也大于a‘所以c和d不肯能是第四小的数。同理也可以排除b数组中的a'和b’.那么数组中就只剩下A数组中的a b和B数组中的c'和d'我们发现我们只要重复上面的过成就可以找到到上中位数。

3.b小于b‘与情况二相反同理可证，各位老铁可以自己下去证明即可

数组长度为奇数时：

在长度为奇数的数组中我们同样按照上面的操作先取出数组A和数组B的上中位数。A数组中的中位数为c 而B数组中的中位数为c'同样的有三种情况：

1.c==c‘那么c一定是上中位数 

2.c大于c'时我们可以排除A数组中的c,d,e是不可能为第五小的数应为c大于a，b,a',b',c'不可能是第六小的数，而B数组中数组中a'和b'不可能是第五小的数。在这里我们发现不等长了A数组中有两个数而B数组中有两个数，解决方案我们只要手动验证c'看它和b的大小关系，如果是则返回如果不是则将其排除此时就变成等长的数组，我们就可以继续调算法原型

3.c<c'和2是同理的

总结：

首先分别找出两个数组arr1和arr2的中位数，分别为mid1,mid2，比较，如果mid1 == mid2，则该数即为所有数的上中位数。
       （1）mid1 > mid2时：
     若数组长度N为偶数时：因为mid1>mid2，所以mid2不可能是所有数的上中位数，arr1中mid1后面的数也不可能是上中位数，  此时两个数组就分别筛选掉了一半，然后递归对arr1的前半部分和arr2的后半部分求所有数的上中位数。
         若数组长度N为奇数时： 因为mid1>mid2，所以mid1不可能是所有数的上中位数，但mid2有可能是，由于球上中位数的两个数组
        必须等长，因此，我们递归对arr1的前半部分(包括mid1)和arr2的后半部分(包括mid2)求所有数的上中位数。
    （ 2) mid1 < mid2时的情况和 2）类似。
 

对应代码：

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. int GetMidNum(vector<int>&nums1,vector<int>&nums2){
  5.            int start1=0;
  6.            int start2=0;
  7.            int end1=nums1.size()-1;
  8.            int end2=nums2.size()-1;
  9.            int mid1=0;
  10.            int mid2=0;
  11.              int offset=0;
  12.            while(start1<end1){
  13.                mid1=(end1+start1)/2;
  14.                mid2=(end2+start2)/2;
  15.                offset=((end1-start1+1)&1)^1;//判断数组的长度是偶数还是奇数
  16.                if(nums1[mid1]>nums2[mid2]){
  17.                      end1=mid1;//变换下标
  18.                       start2=mid2+offset;
  19.                }
  20.                else if(nums1[mid1]<nums2[mid2]){
  21.                    start1=mid1+offset;
  22.                    end2=mid2;
  23.                }
  24.                else{
  25.                    return nums1[mid1];
  26.                }
  27.            }
  28.            return min(nums1[start1],nums2[start2]);//返回最小的那一个
  29. }
  30. int main(){
  31.     int n;
  32.     cin>>n;
  33.      vector<int>arr1(n);
  34.     vector<int>arr2(n);
  35.     for(int i=0;i<n;i++){
  36.         cin>>arr1[i];
  37.     }
  38.     for(int i=0;i<n;i++){
  39.         cin>>arr2[i];
  40.     }
  41.     cout<<GetMidNum(arr1,arr2);
  42.     return 0;
  43. }

下面我们在来看一个加强版的：

对应牛客网链接：
https://www.nowcoder.com/practice/b933e6a7924c44388fc08e807945f6c7?tpId=101&&tqId=33150&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D101%26type%3D101%26page%3D1

题目描述：

给定两个有序数组arr1和arr2，再给定一个整数K，返回所有数中第K小的数。

[要求]

如果arr1的长度为N，arr2的长度为M，时间复杂度请达到O(\log(\min{N, M}))O(log(minN,M))，额外空间复杂度O(1)O(1)。

第一行三个整数N, M, K分别表示数组arr1, arr2的大小，以及需要询问的数
接下来一行N个整数，表示arr1内的元素
再接下来一行M个整数，表示arr2内的元素

输出一个整数表示答案

输入：

  1. 5 3 1
  2. 1 2 3 4 5
  3. 3 4 5

复制输出：

复制说明：

  1. 1是所有数中第一小的数

输入：

  1. 3 4 4
  2. 1 2 3
  3. 3 4 5 6

复制输出：

  1. 3

复制说明：

  1. 3是所有数中第4小的数，所以返回3

解题思路：

1.当两个数组等长时我们可以调用上面的那一题的算法原型即可

2.当两个数组不等长时又分为两种情况

2.1 当k大于两个数组中长的那一个数组的长度时

假设我们要求第23小的数我们首先就可以排除1‘到到12’都是不可能的这是因为就算法他们都比A数组中的元素大也不可能是第23小的数

同理A中的1 2 3 4 5也是不可能的此时A数组中可能的元素和B中可能的元素的个数相同，那我们是不是可以调前面那个算法原型呢？假设可以我们在这10个数里面找到上中位数也就是这十个数里面第5小的数，我们可以计算一下前面比这个上中位数小的一共是17+4=21,此时并不是23小。

我们在这里需要将13‘和10做比较，将6和17做比较看他们两是不是上中位数。如果是则直接返回，如果不是我们此时只需要在剩下的8个数中找到第4小的数，这样计算一下发现刚好是第23小的数

2.2 k小于长数组的长度但是小于短数组的长度

假设我们要求第15小的数和上面同样的我们现在A数组中看那些数不可能首先A数组中所有的数都有可能

B数组中1’到4‘和16’到17‘是不可能是第十五小的数

我们发现B数组中可能的数有5’到15‘一共11个数而A数组中只有10个数长度不相等，此时我们手动验一下5’看它是否大于10如果大于则是第15小的数如果不是则将其排除就刚10个数和A数组等长，调用算法原型即可

对应代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. //算法原型
  6.   int GetMidNum(vector<int>&nums1,int start1,int end1,vector<int>&nums2,int start2,int end2){
  8.            int mid1=0;
  9.            int mid2=0;
  10.              int offset=0;
  11.            while(start1<end1){
  12.                mid1=(end1+start1)/2;
  13.                mid2=(end2+start2)/2;
  14.                offset=((end1-start1+1)&1)^1;//判断长度是奇数还是偶数
  15.                if(nums1[mid1]>nums2[mid2]){
  16.                      end1=mid1;
  17.                       start2=mid2+offset;
  18.                }
  19.                else if(nums1[mid1]<nums2[mid2]){
  20.                    start1=mid1+offset;
  21.                    end2=mid2;
  22.                }
  23.                else{
  24.                    return nums1[mid1];
  25.                }
  26.            }
  27.            return min(nums1[start1],nums2[start2]);
  28. }
  30. int findKthNum(vector<int>&arr1,vector<int>&arr2,int k){
  31.     vector<int>longs=arr1.size()>=arr2.size()?arr1:arr2;//长数组
  32.     vector<int>shorts=arr1.size()<arr2.size()?arr1:arr2;//短数组
  33.      int shortLenth=shorts.size();
  34.       int longLenth=longs.size();
  35.       if(k<=shortLenth){//情况1小于短数组的长度
  36.           return GetMidNum(shorts,0,k-1,longs,0,k-1);
  37.       }
  38. //情况二中的小情况1大于长数组的长度
  39.      if(k>longLenth){
  40.          if(shorts[k-longLenth-1]>=longs[longLenth-1]){//手动验证
  41.              return shorts[k-longLenth-1];
  42.          }
  43.          if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){//手动验证
  44.              return longs[k-shortLenth-1];
  45.          }
  46. //算法原型
  47.   return GetMidNum(shorts,k-longLenth,shortLenth-1,longs,k-shortLenth,longLenth-1);
  48.      }
  49. //情况二中的小情况1：大于短数组的长度但是小于短数组的长度
  50.     if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){//手动排除长数组中的一个
  51.         return longs[k-shortLenth-1];
  52.     }
  54.     return GetMidNum(shorts,0,shortLenth-1,longs,k-shortLenth,longLenth-1);
  55. }
  56.     
  57. int main(){
  58.     int N,M,k;
  59.     cin>>N>>M>>k;
  60.     vector<int>arr1(N);
  61.     for(int i=0;i<N;i++){
  62.         cin>>arr1[i];
  63.             }
  64.     vector<int>arr2(M);
  65.     for(int i=0;i<M;i++){
  66.         cin>>arr2[i];
  67.     }
  68.     cout<<findKthNum(arr1, arr2, k);
  69.     
  70.     return 0;
  71. }

有了上面的基础我们用这个题来秒杀几个题：

对应牛客网链接：多数组中位数_牛客题霸_牛客网 (nowcoder.com)

题目描述：

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

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

输入：

  1. [1,2,3],[3,4,5]

返回值：

  1. 3

输入：

  1. [1,2,3],[4,5]

复制返回值：

  1. 3

解题思路：假设两个数组的总长度为len。如果len为偶数则下中位数为第len/2小的数，如果为奇数则为第len/2+1小的数

对应代码：

  1. class Solution {
  2. public:
  3.     int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
  4.         // write code here
  5.           int len=(arr1.size()+arr2.size())/2;
  6.           if(((arr1.size()+arr2.size())&1)==0){//判断奇数还是偶数长度
  7.                len--;
  8.           }
  9.         return findKthNum(arr1,arr2, len+1);
  10.     }
  11.       int GetMidNum(vector<int>&nums1,int start1,int end1,vector<int>&nums2,int start2,int end2){
  13.            int mid1=0;
  14.            int mid2=0;
  15.              int offset=0;
  16.            while(start1<end1){
  17.                mid1=(end1+start1)/2;
  18.                mid2=(end2+start2)/2;
  19.                offset=((end1-start1+1)&1)^1;
  20.                if(nums1[mid1]>nums2[mid2]){
  21.                      end1=mid1;
  22.                       start2=mid2+offset;
  23.                }
  24.                else if(nums1[mid1]<nums2[mid2]){
  25.                    start1=mid1+offset;
  26.                    end2=mid2;
  27.                }
  28.                else{
  29.                    return nums1[mid1];
  30.                }
  31.            }
  32.            return min(nums1[start1],nums2[start2]);
  33. }
  34. int findKthNum(vector<int>&arr1,vector<int>&arr2,int k){
  35.     vector<int>longs=arr1.size()>=arr2.size()?arr1:arr2;
  36.     vector<int>shorts=arr1.size()<arr2.size()?arr1:arr2;
  37.      int shortLenth=shorts.size();
  38.       int longLenth=longs.size();
  39.       if(k<=shortLenth){
  40.           return GetMidNum(shorts,0,k-1,longs,0,k-1);
  41.       }
  42.      if(k>longLenth){
  43.          if(shorts[k-longLenth-1]>=longs[longLenth-1]){
  44.              return shorts[k-longLenth-1];
  45.          }
  46.          if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
  47.              return longs[k-shortLenth-1];
  48.          }
  49.   return GetMidNum(shorts,k-longLenth,shortLenth-1,longs,k-shortLenth,longLenth-1);
  50.    }
  51.     
  52.     if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
  53.         return longs[k-shortLenth-1];
  54.     }
  55.     return GetMidNum(shorts,0,shortLenth-1,longs,k-shortLenth,k-1);
  56. }
  57. };

我们再来看：

对应letecode链接：
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/

题目描述：

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

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

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解题思路和上题一样：会了前面两个题这两个题可以秒杀

对应代码：

  1. class Solution {
  2. public:
  3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  4.                 int len=(nums1.size()+nums2.size());
  5.                 bool even=(len&1)==0;//判断是奇数还是偶数
  6.                 if(nums1.size()!=0&&nums2.size()!=0){
  7.                     if(even){
  8.            return ( findKthNum(nums1,nums2,len/2)+findKthNum(nums1,nums2,len/2+1) )/2.0;//中间两个除二
  9.                     }
  10.                     else{//奇数
  11.                         return findKthNum(nums1,nums2,len/2+1);
  12.                     }
  13.                 }
  14.                 if(nums2.size()==0){
  16.                     if(even){
  17.                         return(double) (nums1[(len-1)/2]+nums1[len/2])/2;
  18.                     }
  19.                     else{
  20.                         return nums1[len/2];
  21.                     }
  22.                 }
  23.                 else if(nums1.size()==0){
  24.                     if(even)
  25.                     return(double)(nums2[(len-1)/2]+nums2[len/2])/2;
  26.                     else{
  27.                         return nums2[len/2];
  28.                     }
  29.                 }
  30.                 //数组长度都为0
  31.                 else{
  32.                     return 0;
  33.                 }
  34.                 
  36.     }
  37.      int GetMidNum(vector<int>&nums1,int start1,int end1,vector<int>&nums2,int start2,int end2){
  39.            int mid1=0;
  40.            int mid2=0;
  41.              int offset=0;
  42.            while(start1<end1){
  43.                mid1=(end1+start1)/2;
  44.                mid2=(end2+start2)/2;
  45.                offset=((end1-start1+1)&1)^1;
  46.                if(nums1[mid1]>nums2[mid2]){
  47.                      end1=mid1;
  48.                       start2=mid2+offset;
  49.                }
  50.                else if(nums1[mid1]<nums2[mid2]){
  51.                    start1=mid1+offset;
  52.                    end2=mid2;
  53.                }
  54.                else{
  55.                    return nums1[mid1];
  56.                }
  57.            }
  58.            return min(nums1[start1],nums2[start2]);
  59. }
  60. int findKthNum(vector<int>&arr1,vector<int>&arr2,int k){
  61.     vector<int>longs=arr1.size()>=arr2.size()?arr1:arr2;
  62.     vector<int>shorts=arr1.size()<arr2.size()?arr1:arr2;
  63.      int shortLenth=shorts.size();
  64.       int longLenth=longs.size();
  65.       if(k<=shortLenth){
  66.           return GetMidNum(shorts,0,k-1,longs,0,k-1);
  67.       }
  68.      if(k>longLenth){
  69.          if(shorts[k-longLenth-1]>=longs[longLenth-1]){
  70.              return shorts[k-longLenth-1];
  71.          }
  72.          if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
  73.              return longs[k-shortLenth-1];
  74.          }
  75.   return GetMidNum(shorts,k-longLenth,shortLenth-1,longs,k-shortLenth,longLenth-1);
  76.    }
  77.     
  78.     if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
  79.         return longs[k-shortLenth-1];
  80.     }
  81.     return GetMidNum(shorts,0,shortLenth-1,longs,k-shortLenth,k-1);
  82. }
  84. };

如果觉得对您有帮助的话劳烦您点个赞，如有错误请在评论区留言 

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_56999918/article/details/122643005

内容来源于网络，如有侵权，请联系作者删除！

c语言职场和发展蓝桥杯

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com