【C++、二分法】LeetCode 4.寻找两个有序数组的中位数

题目：

给定两个大小为 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

二分法，先找到第K小的数，再计算中位数，C++代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), mid = (m + n) / 2;
        if ((m + n) % 2) {//两个容器总共有奇数个数
            return findKth(nums1, nums2, mid + 1);
        }
        else {//两个容器总共有偶数个数
            return (0.0 + findKth(nums1, nums2, mid) + findKth(nums1, nums2, mid + 1)) / 2;
        }
    }

private:
    vector<int> ret;
    vector<int> vectorAdd(vector<int> nums, int n)
    {
        ret.clear();
        ret.assign(nums.begin() + n, nums.end());
        return ret;
    }


    int findKth(vector<int> nums1, vector<int> nums2, int k) {

        int m = nums1.size(), n = nums2.size();
        if (m > n) return findKth(nums2, nums1, k);
        if (m == 0) return nums2[k - 1];
        if (k == 1) {
            int t = min(nums1[0], nums2[0]);
            //cout << "nums1[0]="<< nums1[0] << "    nums2[0]=" << nums2[0] <<"   min(nums1[0], nums2[0])="<<t << endl;
            return t /*min(nums1[0], nums2[0])*/;
        }

        int pa = min(k / 2, m), pb = k - pa;
        if (nums1[pa - 1] < nums2[pb - 1]) {
            return findKth(vectorAdd(nums1, pa), nums2, k - pa);
        }
        else if (nums1[pa-1] > nums2[pb-1]) {
            return findKth(nums1, vectorAdd(nums2, pb), k - pb);
        }
        else {
            return nums1[pa - 1];
        }
    }
};

注释版本：

class Solution {
public:
    double 找中位数(数组1, 数组2) {
        int m = 数组1的长度, n = 数组2的长度, mid = 数组1长度和数组2长度的平均数;
        if ((数组1的长度+数组2的长度)模2得到的不是0，而是1) {//两个容器总共有奇数个数
            return 找第K大(数组1, 数组2, 中间值+1);
        }
        else {//两个容器总共有偶数个数
            return (0.0 + 找第K大(数组1, 数组2, 中间值) + 找第K大(数组1, 数组2, 中间值 + 1)) / 2得到两次计算得到的第K大的数的平均值;
        }
    }

private:
    vector<int> ret 该数组用于保存结果;
    vector<int> 取一个数组的从第n个位置开始之后的子数组(vector<int> nums, int n)
    {
        清空ret;
        将nums的指定范围的子数组赋值给ret(从nums数组的第n个元素开始, 到nums数组的尾后位置结束);
        返回ret;
    }

    int 找到第K大(数组1, 数组2, k) {
        int m = 数组1的长度, n = 数组2的长度;
        
        if (数组1更长) return 找到第K大(数组2, 数组1, k);
        
        if (数组1为空) return 数组2[k-1];
       
        if (要求找第1大的数（或者说找第1小的数）) {
            int t = 找到 数组1第1个数 和 数组2第1个数 的最小值;
            return t;
        }

        int pa = 找最小值(k / 2, 数组1的长度), pb = k - pa;
        if (数组1[pa - 1] < 数组2[pb - 1]) {
            return 找到第K大(取数组1从第pa个位置开始之后的子数组, 数组2, k-pa);
        }
        else if (数组1[pa-1] > 数组2[pb-1]) {
            return 找到第K大(数组1, 取数组2从第pb个位置开始之后的子数组, k-pb);
        }
        else {
            return 数组1[pa-1];
        }
    }
};