LeetCode 寻找两个有序数组的中位数(二分法)
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
思路分析:对于时间复杂度限制在O(log2(m + n)),非常具有挑战性,我们这里先介绍一种时间复杂度为O(m + n)级别的算法实现。
我们先将两个有序数组进行合并放入myMergeVec,并且合并的个数是sum / 2 + 1 (sum为两个数组的大小之和)
如果sum 是偶数,中位数就是 myMergeVec[sum / 2 - 1] 和 myMergeVec[sum / 2]平均值
否则中位数就是myMergeVec[sum / 2]
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int indexOne = 0, indexTwo = 0, numsOneSize = nums1.size(), numsTwoSize = nums2.size();
int sumSize = numsOneSize + numsTwoSize, cnt = 0;//cnt用于已经合并好的数据个数
vector<int> mySortVec(sumSize / 2 + 1, 0);//合并后的数组
//两个指针分别扫描两个指针
while (cnt <= sumSize / 2 && indexOne < numsOneSize && indexTwo < numsTwoSize){
//每次都取较小的元素放入合并中数组,从而维持合并数组的有序性
if (nums1[indexOne] < nums2[indexTwo]){
mySortVec[cnt++] = nums1[indexOne++];
}
else{
mySortVec[cnt++] = nums2[indexTwo++];
}
}
//下面两个while至多执行一个,因为上面的循环退出,必定会满足一个条件
//合并的个数没有达到sumSize / 2 + 1,且数组一还有剩余
while (cnt <= sumSize / 2 && indexOne < numsOneSize){
mySortVec[cnt++] = nums1[indexOne++];
}
//合并的个数没有达到sumSize / 2 + 1,且数组二还有剩余
while (cnt <= sumSize / 2 && indexTwo < numsTwoSize){
mySortVec[cnt++] = nums2[indexTwo++];
}
//然后就是分sumSize的奇偶性,取结果
if (sumSize % 2 == 0){
return (mySortVec[sumSize / 2 - 1] + mySortVec[sumSize / 2]) / 2.0;
}
else{
return mySortVec[sumSize / 2];
}
}
};
方法二:使用二分法。首先我们知道中位数处在排序两个数组后的中间位置,如果两个数组sum大小和为奇数,最中间的就是第sum / 2 + 1个数,否则就是 sum / 2 和sum / 2 + 1这两个数的平均数。进而问题转化为求两个序列的最中间的数。
(下面的代码是搬评论区大神的,只是加上了注释)
下面初略的证明一下,处理一、二处为什么可以进行判定不在对应的区间内。
class Solution {
public:
double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
int m = A.size();
int n = B.size();
int total = m + n;
if (total % 2 == 1) {// 奇数
return find_kth(A.begin(), m, B.begin(), n, total/2 + 1);//直接找最中间的数
}
else {
//偶数,寻找最中间的两个数
return (find_kth(A.begin(), m, B.begin(), n, total/2) + find_kth(A.begin(), m, B.begin(), n, total/2 + 1))/2.0;
}
}
int find_kth(vector<int>::const_iterator A, int m, vector<int>::const_iterator B, int n, int k) {
//确保m <= n
if (m > n) {
return find_kth(B, n, A, m, k);
}
// A为空,直接找B中第k个
if (m == 0){
return *(B + k - 1);
}
// 若k==1,比较A[0],B[0],取最小
if (k == 1){
return min(*A, *B);
}
//将k分成两个部分
int ia = min(k / 2, m), ib = k - ia;
if (*(A + ia - 1) < *(B + ib - 1)) {
// A[ia-1] < B[ib-1] A的前ia个舍去,再在剩余A和原来B中找第K-ia小的
//处理一:第k个数必定不会出现在[ia, A + ia - 1]
return find_kth(A + ia, m - ia, B, n, k - ia);
}
else if (*(A + ia - 1) > *(B + ib - 1)) {
// A[ia-1] > B[ib-1] B的前ib个舍去,再在剩余B和原来A中找第K-ib小的
//处理二:第k个数必定不会出现在[ib, B + ib - 1]
return find_kth(A, m, B + ib, n - ib, k - ib);
}
else {// 若二者相等直接返回
return A[ia - 1];
}
}
};