int findKthEle( vector<int> & nums1, vector<int> & nums2, int k )
{
int first = max( 0, k - nums2.size() ), last = min( nums1.size(), k );
/* 我们寻找的是满足a[i-1]<=b[j]&&b[j-1]<=a[i]的最小的位置i */
while ( first < last )
{
int mid = first + (last - first) / 2;
/*
* m=i，j=k-m,所以i+j=k，k-m-1相当于j-1即j前一个位置。j-1比i位置的值大，需要排除
* 只需判断 b[j-1]<=a[i] 这个条件
* 因为找的是最小的i，j=k-i是所有满足b[j-1]<=a[i]中相对最大的
* 如果它不满足其他的也不可能满足另一个条件
* 所以一定满足a[i-1]<=b[j]，不满足的都会在逼近过程中排除
*/
if ( nums2[k - mid - 1] > nums1[mid] )
first = mid + 1;
else last = mid;
}
/*
* 循环结束时的位置first即为所求位置
* 第k小即为max(nums1[first-1]),nums2[k-first-1])
* 但是由于le可以为0、k，first-1或者k-first-1可能不存在
*/
int nums1_max = first == 0 ? INT_MIN : nums1[first - 1];
int nums2_max = first == k ? INT_MIN : nums2[k - first - 1];
return(max( nums1_max, nums2_max ) );
}
double findMedianSortedArrays( vector<int> & nums1, vector<int> & nums2 )
{
int n = nums1.size() + nums2.size();
double median;
if ( n & 1 ) /* 奇数 */
{
median = findKthEle( nums1, nums2, n / 2 + 1 );
} else { /* 偶数 */
median = (findKthEle( nums1, nums2, n / 2 ) + findKthEle( nums1, nums2, n / 2 + 1 ) ) / 2.0;
}
return(median);
}
2020-02-05
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
