[LC-4][chapter4][Binary] Median of Two Sorted Arrays 寻找两个正序数组的中位数

[renchord]

Tag:二分法 题目链接 ： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ 题目描述： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2：

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5   提示：

nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106

题解： (1)最简单的写法是O(m+n)的，在此不细说。 (2)题目可以泛化为一个算法为，寻找两个sored array中合计前K大的数字，如果我们每次都能处理一半的K，则复杂度可以成对数级别下降。 提供一个method为 ： 寻找数组 [A, A + m) 和数组 [B, B + n) 中前K大的数字，分析下来我们可以有以下几个情况：

情况一： m > n， 此时我们交换 A B两个数组； 情况二: 0 == m， 即当前数组A已经空了，则我们只需要返回 (B + K - 1)对应的数字即可； 情况三: 1 == K, 即此时只有一个数需要找，我们找 (A) 和 (B) 中较小的一个即可； 情况四： 都不满足上列情况，则需要递归处理，方式如下： 将 K除以2， 与当前m比较， A需要移动 ia = min(K / 2, m)大小，而B则需要移动 ib = K - ia的大小； 假设偏移后的位置分别为 (A + ia - 1) 和 *(B + ib - 1)， 比较这两个数的大小，如果A数组中的小，我们可以把A数组偏移掉的这一部分的数字去掉，如果B数组中的小，我们可以把B数组中偏移掉的一部分去掉，此外证明两数相等，我们已经找到了需要的数字； 如果去掉A数组中的数字，则迭代调用这个method，此时需要更新A、m和K； 如果去掉B数组中的数字，则递归调用这个method，此时需要更新B、n和K；

最后，我们需要判断初始条件中m + n （两个数组长度）是奇数还是偶数，奇数的话 K = (m + n) / 2 + 1, 偶数的话分别要计算出 前K = （m+ n） /2 和 前 K = (m+ n )/2 + 1 时两个数的平均值；

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        int m = nums1.size();
        int n = nums2.size();

        if(total % 2 == 0)
            return (find_kth(nums1.begin(), m, nums2.begin(), n, total / 2) + find_kth(nums1.begin(), m, nums2.begin(), n, total / 2 + 1)) / 2.0;
        else
            return find_kth(nums1.begin(), m, nums2.begin(), n, total / 2 + 1);
    }

    static int find_kth(std::vector<int>::const_iterator A, int m, std::vector<int>::const_iterator B, int n, int k)
    {
        if (m > n)
            return find_kth(B, n, A, m, k);
        if (m == 0)
            return *(B + k - 1);
        if (k == 1)
            return min(*(A + k - 1), *(B + k - 1));

        int ia = min(k / 2, m);
        int ib = k - ia;

        if(*(A + ia - 1) < *(B + ib - 1))
            return find_kth(A + ia, m - ia, B, n, k - ia);
        else if(*(A + ia - 1) > *(B + ib - 1))
            return find_kth(A, m, B + ib, n - ib, k - ib);
        return 
            *(A + ia - 1);
    }
};