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