C++ 中两个已排序数组的中位数
假设我们有两个数组;这两个数组是已排序的。因此，我们需要找到这两个数组的中位数。如果这两个数组分别是 [1,5,8] 和 [2,3,6,9]，那么答案就是 5。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 findMedianSortedArrays，它将接收 nums1 和 nums2 数组作为参数
如果 nums1 的大小 > nums2 的大小，然后
调用函数返回 findMedianSortedArrays(nums2, nums1)
x := nums1 的大小，y := nums2 的大小
low := 0, high := x
totalLength := x + y
当 low<=high 时，执行 −
partitionX := low + (high - low) / 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，则
如果totalLength mod 2等于0，则
返回 (maxLeftX 和 maxLeftY 中的最大值) + minRightX 和 minRightY 中的最小值) / 2
否则
返回 maxLeftX 和 maxLeftY 中的最大值
否则，当 maxLeftX>minRightY 时，则 −
high := partionX - 1
否则，low := partionX + 1
return 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
