在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
如果totalLengthmod2与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