这道题的最优解的解题方式很巧妙，不需要合并数组，采用二分思想来取得中间值，将时间复杂度降到了 $O(\log(m+n))$。当然，本题也是有常见的 $O(m+n)$ 的做法。
题目
力扣：4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n)) 。
题解
归并
归并将两个有序数组合并为一个有序数组，利用双指针分别指向 nums1、nums2，循环比较当前指向的元素，将较小的元素放入新数组中。当一个数组放完就将剩下数组的元素全部放入新数组中。
此时新数组是一个有序列，其的中间值就是对应的中位数。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
double findMedianSortedArrays(std::vector<int> &nums1, std::vector<int> &nums2)
{
std::vector<int> merged;
int mid;
int i = 0, j = 0, k;
while (i < nums1.size() && j < nums2.size())
{
if (nums1[i] < nums2[j])
{
merged.push_back(nums1[i]);
i++;
}
else
{
merged.push_back(nums2[j]);
j++;
}
}
for (k = i; k < nums1.size(); k++)
merged.push_back(nums1[k]);
for (k = j; k < nums2.size(); k++)
merged.push_back(nums2[k]);
mid = merged.size() / 2;
if (merged.size() % 2 == 1)
return merged[mid];
else
return double(merged[mid - 1] + merged[mid]) / 2;
}
|
双指针
通过 i 和 j 指针移动比较小的元素移动 total / 2 + 1 次，这样 curr 就代表中间值了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
double findMedianSortedArrays(std::vector<int> &nums1, std::vector<int> &nums2)
{
int total = nums1.size() + nums2.size();
int i = 0, j = 0, k;
int prev, curr;
for (k = 0; k < total / 2 + 1; k++)
{
prev = curr;
if (i < nums1.size() && (j > nums2.size() || nums1[i] < nums2[j]))
{
curr = nums1[i];
i++;
}
else
{
curr = nums2[j];
j++;
}
}
if (total % 2 == 1)
return curr;
else
return double(curr + prev) / 2;
}
|
二分切割
这种方法比较巧妙。
因为两个数组皆有序，所以当确定第一个数组位于中位数左边的数有 n 个，则第二个数组的第 len(nums2) - ((total/2+1) - n) 就是中位数，如此以来就很好解决。
我们可以通过两个数组长度推断出需要分割的数量，而对于分割点只要做到：
1
2
|
left1 < right2
left2 < right2
|
即可求得中位数，否则就按二分进行缩小取值。
如图所示：
而且只需要二分较短的那个数组即可，如果该数组全被分割，则可以通过 total/2+1-len(nums1) 的值来求得中位数在较长数组的取值。，实际就要确定较短数组的位置，在最开始用 std::swap 来进行确定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
double findMedianSortedArrays(std::vector<int> &nums1, std::vector<int> &nums2)
{
if (nums1.size() > nums2.size())
std::swap(nums1, nums2);
int low = 0, height = nums1.size();
int i, j;
int left1, left2, right1, right2;
while (low <= height)
{
i = low + (height - low) / 2;
j = (nums1.size() + nums2.size() + 1) / 2 - i;
i > 0 ? left1 = nums1[i - 1] : left1 = INT_MIN;
i < nums1.size() ? right1 = nums1[i] : right1 = INT_MAX;
j > 0 ? left2 = nums2[j - 1] : left2 = INT_MIN;
j < nums2.size() ? right2 = nums2[j] : right2 = INT_MAX;
if (left1 <= right2 && left2 <= right1)
{
if ((nums1.size() + nums2.size()) % 2 == 1)
return std::max(left1, left2);
return double(std::max(left1, left2) + std::min(right1, right2)) / 2;
}
else if (left1 > right2)
height = i - 1;
else
low = i + 1;
}
}
|
可以看到 low 和 height 两者用于二分 nums1。
1
2
3
4
|
i > 0 ? left1 = nums1[i - 1] : left1 = INT_MIN;
i < nums1.size() ? right1 = nums1[i] : right1 = INT_MAX;
j > 0 ? left2 = nums2[j - 1] : left2 = INT_MIN;
j < nums2.size() ? right2 = nums2[j] : right2 = INT_MAX;
|
假如分割点到了边界就应该分配正无穷或负无穷确保后续判断正确。