【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);
        }
    }
};