题解 | #牛的体重排序#

考察知识点：二分

题目分析：

题目要求用O(log(m + n))的时间复杂度解决问题，应该考虑二分。由于两个序列都是有序的，找中位数就是找到中间的第k个数。

首先我们假设weightsA的长度小于weightsB的长度。

为了能找到第k个数，我们设法每一次排除k / 2个数。可以分别在数组A和B中找到第k / 2个数。

上例中30 > 20，所以20以及之前的数都不可能是第k个数，所以B中就不再考虑10和20，那么k只需要找第4 - 2 = 2个数即可。

那么我们分别在A和B中找到第2 / 2 = 1个数，发现10 < 30，所以A中10可以排除，K只需要找第一个数。

第一个数就取A和B中较小的那一个，上述例子中刚好都是30。最终结果就是30。

当出现A数组中的数太少，k / 2大于A数组中数的个数时，由于A数组中的数可能比较大，需要用最后一个数与B数组中的第k / 2个数进行比较来排除。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型vector 
     * @param weightsB int整型vector 
     * @return double浮点型
     */
    int getKth(vector<int> &numsA, int la, int ra, vector<int> &numsB, int lb, int rb, int k) {
        int len1 = ra - la + 1;
        int len2 = rb - lb + 1;

        if (len1 > len2) return getKth(numsB, lb, rb, numsA, la, ra, k);
        if (len1 == 0) return numsB[lb + k - 1];

        if (k == 1) return min(numsA[la], numsB[lb]);

        int i = la + min(len1, k / 2) - 1;
        int j = lb + min(len2, k / 2) - 1;
        if (numsA[i] > numsB[j]) 
            return getKth(numsA, la, ra, numsB, j + 1, rb, k - (j - lb + 1));
        else 
            return getKth(numsA, i + 1, ra, numsB, lb, rb, k - (i - la + 1));
    }
    double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        int sizeA = weightsA.size();
        int sizeB = weightsB.size();
        int size = sizeA + sizeB;
        int evenK = (size + 2) / 2;
        int k = (size + 1) / 2;
        return (getKth(weightsA, 0, sizeA - 1, weightsB, 0, sizeB - 1, k) + getKth(weightsA, 0, sizeA - 1, weightsB, 0, sizeB - 1, evenK)) * 0.5;
    }
};