【leetcode】寻找两个有序数组的中位数【C++】
题目如下:
解题思路:
因为时间复杂度要求为 O( log(m+n) ),所以显然需要采用二分或者分治的方法来做,这题参考找第 k 个数的思想来做,每次排除 k/2 个数,时间复杂化度 O(logk) 。
查找两个已排序数组所有元素第k大的数。假定A、B的元素个数都大于k/2,将A和B的第k/2个元素进行比较。三种情况:
1、A[k/2-1] == B[k/2-1]
2、A[k/2-1] > B[k/2-1]
3、A[k/2-1] < B[k/2-1]
- 如果A[k/2-1] < B[k/2-1],则A[0]到A[k/2-1]必在topK元素内,可以删除A数组的这k/2个元素;对B同理。继续递归调用。
- 当A[k/2-1] == B[k/2-1]时,找到了第k大的元素,返回之。
- 递归函数的终止条件:
1、当A(B)为空,直接返回B[k-1](A[k-1]);
2、当k=1时,返回min(A[0], B[0]);
代码如下(C++):
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//用查找第"k"个数的思想来做(数组的第一个元素从1开始计数)
int n = nums1.size(), m = nums2.size();
//注意C++中奇数直接除以2后并不是中位数,需要加1,例如 5 / 2 = 2;
int len = (n + m) / 2 + 1;
//按奇偶讨论
if ((n + m) % 2 == 1){
return findK(nums1, 0, nums2, 0, len);
}
else{
return (findK(nums1, 0, nums2, 0, len - 1) + findK(nums1, 0, nums2, 0, len)) / 2.0;
}
}
//i和j为A、B数组的起始位置
//注意k相对数组是从1开始计数的,代表元素的真实排序位置
//而i、j相对数组是从0开始计数的,代表元素在数组中的索引位置
int findK(vector<int> A, int i, vector<int> B, int j, int k) {
//一个数组全都被舍弃后直接返回
if (i >= A.size()){
return B[j + k - 1];
}
if (j >= B.size()){
return A[i + k - 1];
}
//边界情况
if (k == 1){
return min(A[i], B[j]);
}
//舍弃较小的前k/2个数
//如果某个数组可能越界就舍弃另一个数组的前k/2个数
int A_key = i + k / 2 - 1 < A.size() ? A[i + k / 2 - 1] : INT_MAX;
int B_key = j + k / 2 - 1 < B.size() ? B[j + k / 2 - 1] : INT_MAX;
//舍弃k/2个数后,问题变为查找第k - k / 2个数
if (A_key < B_key){
return findK(A, i + k / 2, B, j, k - k / 2);
}else{
return findK(A, i, B, j + k / 2, k - k / 2);
}
}
};