数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：查找两个已排序列表的中位数
假设我们有两个已排序的列表。我们需要找到这两个列表的中位数。例如，如果数组为[1,5,8]和[2,3,6,9]，则答案为5。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数solve()，它将接收数组nums1和数组nums2作为参数。
- 如果nums1的大小大于nums2的大小，则
- 返回solve(nums2, nums1)
- x := nums1的大小，y := nums2的大小
- low := 0，high := x
- totalLength := x + y
- 当low <= high时，执行以下操作：
- partitionX := low + (high - low)
- 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，则
- 如果totalLength模2等于0，则
- 返回((maxLeftX和maxLeftY中的最大值) + (minRightX和minRightY中的最小值)) / 2
- 否则
- 返回maxLeftX和maxLeftY中的最大值
- 如果totalLength模2等于0，则
- 否则，如果maxLeftX > minRightY，则
- high := partitionX - 1
- 否则
- 返回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
更新于：2020年11月26日
174 次浏览
广告