两个有序数组中的中位数以及求第k个最小数的值

解法参考

《【分步详解】两个有序数组中的中位数和Top K问题》

https://blog.csdn.net/hk2291976/article/details/51107778

里面求中位数的方法很巧妙,非常值得借鉴,这里写一个用类似思想实现 求第k个最小数的值

这里没有虚加 #,因为求k个最小数的值 不需要考虑 奇偶问题,所以更简单,代码如下:

//[2,3,5]  [1 4 7 9] 第k个小的树的数,比如k=3 那么就返回3
int findTopKSortedArrays(vector<int>& nums1, vector<int>& nums2,int k){
int n = (int)nums1.size();
int m = (int)nums2.size();
if(n > m) //保证数组1一定最短
return findTopKSortedArrays(nums2,nums1,k); //先判断几个特殊情况
if(k==){
return min(nums1[],nums2[]);
}
int lo = ;
int hi=n-;//最后一个索引
//每个数组所包含的元素数目
int c1=;
int c2=;
int L1,R1,L2,R2;
while (lo<=hi) {
//先取中间索引
int midIndex=(lo+hi)/;
//第一个数组所包含的元素个数
c1 = midIndex +;
//第二个数组中所包含的元素个数
c2= k-c1;
//第一个数组确定分割
if(c1==){ //说明第一个数组里没有包含前k个小的元素
L1=INT_MIN;
}
else { // 正常情况,取中间元素作为左边界
L1= nums1[midIndex];
}
if(c1==nums1.size()){//说明第一个数组中的所有元素都在前k个
R1=INT_MAX;
}
else {//正常情况,取中间元素的右边那个作右边界
R1=nums1[midIndex+];
} //第二个数组确定分割
if(c2==){
L2=INT_MIN;
}
else {
L2= nums2[c2-];
}
if(c2==nums2.size()){
R2=INT_MAX;
}
else {
R2=nums2[c2];
} if(L1 > R2){//第一个数组应该减小
hi = midIndex-;
if(hi<){//说明 第一个数组里面没有可用的元素了,返回第二个数组的
return nums2[k-];
}
}
else if(L2 > R1){ //第二个数组的左边界大约第一个数组的有边界,说明第一个数组要右二分
lo = midIndex+;
if(lo==nums1.size()){ //说明 第一个数组里面没有可用的元素了,返回第二个数组的
return nums2[k-];
}
}
else{
break; //符合条件了,跳出
}
}
return max(nums1[c1-],nums2[c2-]); }
上一篇:n个元素的数组向左循环移动i个位置


下一篇:Apache-Tika解析JPEG文档