C ++中两个排序数组的中位数
为了解决这个问题，我们将遵循以下步骤-
定义一个函数findMedianSortedArrays，它将使用nums1和nums2数组
如果nums1的大小>nums2的大小，那么，
调用函数returnfindMedianSortedArrays(nums2,nums1)
x：=nums1的大小，y：=nums2的大小
低：=0，高：=x
totalLength：=x+y
当低<=高时，执行-
高：=partitionX-1
如果totalLengthmod2与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