题解 | #牛的体重排序#

#include <climits>
#include <random>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型vector 
     * @param weightsB int整型vector 
     * @return double浮点型
     */
    double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        if (weightsA.size() == 0) {
            if (weightsB.size() % 2 == 0) {
                return (double)(weightsB[weightsB.size()/2-1] + weightsB[weightsB.size()/2])/2;
            }
            return (double)weightsB[weightsB.size()/2];
        }
        if (weightsB.size() == 0) {
            if (weightsA.size() % 2 == 0) {
                return (double)(weightsA[weightsA.size()/2-1] + weightsA[weightsA.size()/2])/2;
            }
            return (double)weightsA[weightsA.size()/2];
        }
        int len = weightsA.size() + weightsB.size();
        if (len %2 == 0) {
            return (getKth(weightsA, 0, weightsB, 0, len/2) + getKth(weightsA, 0, weightsB, 0, len/2+1))/2.0;
        }
        return getKth(weightsA, 0, weightsB, 0, len/2+1);
    }
    // 找第k个元素，如果不够比较的，后面补整形最大值
    double getKth(vector<int>& weightsA, int beginA, vector<int>& weightsB, int beginB, int k) {
        // 直接从B中找到第k个
        if (beginA >= weightsA.size()) {
            return weightsB[beginB+k-1];
        }
        // 直接从A中找第k个
        if (beginB >= weightsB.size()) {
            return weightsA[beginA+k-1];
        }
        if (k==1) {
            return min(weightsA[beginA], weightsB[beginB]);
        }
        // 如果k/2超过了数组长度，就假定后面所有的数字都是INT_MAX，不影响最终结果
        int k_2_num_a = INT_MAX;
        int k_2_num_b = INT_MAX;
        if (beginA + k/2-1 < weightsA.size()) k_2_num_a = weightsA[beginA+k/2-1];
        if (beginB + k/2-1 < weightsB.size()) k_2_num_b = weightsB[beginB+k/2-1];
        if (k_2_num_a < k_2_num_b) {
            return getKth(weightsA, beginA+k/2, weightsB, beginB, k - k/2);
        }
        return getKth(weightsA, beginA, weightsB, beginB+k/2, k-k/2);
    }
};