在C++中查找两个排序列表的中位数的程序

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

为了解决这个问题，我们将按照以下步骤操作：

• 定义一个函数solve()，这将需要一个数组 nums1，一个数组 nums2，

• 如果 nums1 的大小 > nums2 的大小，则：

• 返回解决(nums2,nums1)

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

• 低：= 0，高：= x

• 总长度：= x + y

• 当低 <= 高时，请执行以下操作：

• 高：= partitionX - 1

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

• 否则

• return ((maxLeftX 和 maxLeftY 的最大值) + (minRightX 和 minRightY 的最小值))/ 2

• 返回 maxLeftX 和 maxLeftY 的最大值

• partitionX := 低 + (高 - 低)

• partitionY := (totalLength + 1) / 2 - partitionX

• maxLeftX := （如果 partitionX 与 0 相同，则为 -inf，否则为 nums1[partitionX - 1]）

• minRightX := （如果 partitionX 与 x 相同，则为 inf，否则为 nums1[partitionX]）

• maxLeftY := （如果 partitionY 与 0 相同，则为 -inf，否则为 nums2[partitionY - 1]）

• minRightY := （如果 partitionY 与 y 相同，则为 inf，否则为 nums2[partitionY]）

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

• 否则当 maxLeftX > minRightY 时，则：

• 否则

• 返回 0

让我们看下面的实现来更好地理解：

示例

#include
using namespace std;

class Solution {
   public:
   double solve(vector& nums1, vector& nums2) {
      if(nums1.size()>nums2.size())
         return solve(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[partitionX-1] );
         int minRightX = (partitionX == x?INT_MAX : nums1[partitionX]);

         int maxLeftY = (partitionY ==0?INT_MIN:nums2[partitionY-1] );
         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 v1 = {1,5,8}, v2 = {2,3,6,9};
   cout << (ob.solve(v1, v2));
}

输入

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

5