C ++中两个排序数组的中位数

假设我们有两个数组；这些数组已排序。因此，我们必须找到这两个数组的中位数。因此，如果数组类似于[1,5,8]和[2,3,6,9]，则答案将为5。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数findMedianSortedArrays，它将使用nums1和nums2数组

• 如果nums1的大小> nums2的大小，那么，

• 调用函数return findMedianSortedArrays(nums2,nums1)

• x：= nums1的大小，y：= nums2的大小

• 低：= 0，高：= x

• totalLength：= x + y

• 当低<=高时，执行-

• 高：= partitionX-1

• 如果totalLength mod 2与0相同，则

• 除此以外

• return（maxLeftX和maxLeftY的最大值）+ minRightX和minRightY的最小值）/ 2

• 返回maxLeftX和maxLeftY的最大值

• partitionX：=低+（高-低）/ 2

• partitionY：=（totalLength + 1）/ 2-partitionX

• 当partitionX为0时，maxLeftX = -inf，否则为nums1 [partitionX-1]

• 当partitionX为x时，maxRightX = inf，否则为nums1 [partitionX]

• 当partitionY为0时，maxLeftY = -inf，否则为nums2 [partitionY-1]

• 当partitionY为y时，maxRightY = inf，否则为nums2 [partitionY]

• 如果maxLeftX <= minRightY并且maxLeftY <= minRightX，则，

• 否则，当maxLeftX> minRightY时，则-

• 否则低：= partitionX + 1

• 返回0

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double findMedianSortedArrays(vector& nums1, vector<int>& nums2) {
      if(nums1.size()>nums2.size())
         return findMedianSortedArrays(nums2,nums1);
      int x = nums1.size();
      int y = nums2.size();
      int low = 0;
      int high = x;
      int totalLength = x+y;
      while(low<=high){
         int partitionX = low + (high - low)/2;
         int partitionY = (totalLength + 1)/2 - partitionX;
         int maxLeftX = (partitionX ==0?INT_MIN:nums1[partitionX1] );
         int minRightX = (partitionX == x?INT_MAX :
         nums1[partitionX]);
         int maxLeftY = (partitionY ==0?INT_MIN:nums2[partitionY1] );
         int minRightY = (partitionY == y?INT_MAX : nums2[partitionY]);
         if(maxLeftX<=minRightY && maxLeftY <= minRightX){
            if(totalLength% 2 == 0){
               return ((double)max(maxLeftX,maxLeftY) + (double)min(minRightX,minRightY))/2;
            } else {
               return max(maxLeftX, maxLeftY);
            }
         }
         else if(maxLeftX>minRightY)
            high = partitionX-1;
         else low = partitionX+1;
      }
      return 0;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {1,5,8}, v2 = {2,3,6,9};
   cout << (ob.findMedianSortedArrays(v1, v2));
}

输入项

[1,5,8]
[2,3,6,9]

输出结果

5