题解 | #牛的体重排序#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是在两个有序数组中找到所有牛的体重的中位数，要求时间复杂度为 O(log (m+n))。

题目解答方法的文字分析

给定两个有序数组 weightsA 和 weightsB，表示牛群A和牛群B的牛的体重，并且数组都按照体重从小到大进行排序。

我们的任务是找出这两个牛群的所有牛的体重的中位数。

为了实现时间复杂度为 O(log (m+n)) 的算法解决此问题，我们可以使用二分法来找到中位数。

中位数的定义：如果两个数组的长度之和是偶数，中位数是两个有序数组合并后的第 (m+n)/2 和 (m+n)/2+1 个元素的平均值；如果长度之和是奇数，中位数是合并后的第 (m+n)/2+1 个元素。

具体步骤如下：

1. 对于合并后的有序数组，如果 m+n 是奇数，我们只需要找到第 (m+n)/2+1 个元素即可；如果 m+n 是偶数，我们需要找到第 (m+n)/2 和 (m+n)/2+1 个元素，然后求平均值。
2. 首先我们假设牛群A的长度 m 小于等于牛群B的长度 n。
3. 我们可以在牛群A中使用二分法找到一个分割线，将牛群A分为两个部分：左侧部分有 i 个元素，右侧部分有 m-i 个元素。
4. 对于牛群B，分割线的位置是 (m+n+1)/2-i。
5. 然后我们需要保证左侧部分的最大元素小于等于右侧部分的最小元素，即 weightsA[i-1] <= weightsB[(m+n+1)/2-i]。
6. 如果上述条件满足，说明分割线位置找对了，我们可以根据 m+n 的奇偶性得到中位数：如果 m+n 是奇数，中位数是 max(weightsA[i-1], weightsB[(m+n+1)/2-i])。如果 m+n 是偶数，中位数是 (max(weightsA[i-1], weightsB[(m+n+1)/2-i]) + min(weightsA[i], weightsB[(m+n+1)/2-i+1])) / 2.0。
7. 如果上述条件不满足，我们需要调整分割线的位置：如果 weightsA[i-1] > weightsB[(m+n+1)/2-i]，说明分割线在牛群A的左侧，我们需要将分割线往左移，令 right = i-1。如果 weightsA[i] < weightsB[(m+n+1)/2-i+1]，说明分割线在牛群A的右侧，我们需要将分割线往右移，令 left = i+1。
8. 重复步骤 3 到步骤 7，直到找到合适的分割线。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型vector 
     * @param weightsB int整型vector 
     * @return double浮点型
     */
    double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        int m = weightsA.size();
        int n = weightsB.size();

        // 确保牛群A的长度 m 小于等于牛群B的长度 n
        if (m > n) {
            return findMedianSortedArrays(weightsB, weightsA);
        }

        int left = 0;
        int right = m;
        int maxLeft = 0, minRight = 0;

        while (left <= right) {
            int i = (left + right) / 2; // 在牛群A中找到分割线的位置
            int j = (m + n + 1) / 2 - i; // 根据分割线位置计算牛群B中对应的位置

            // 计算分割线左侧和右侧的最大和最小值
            int maxLeftA = (i == 0) ? INT_MIN : weightsA[i - 1];
            int minRightA = (i == m) ? INT_MAX : weightsA[i];
            int maxLeftB = (j == 0) ? INT_MIN : weightsB[j - 1];
            int minRightB = (j == n) ? INT_MAX : weightsB[j];

            // 判断是否找到合适的分割线
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
                if ((m + n) % 2 == 0) {
                    // 如果牛群A和牛群B的总长度是偶数，计算中位数
                    maxLeft = max(maxLeftA, maxLeftB);
                    minRight = min(minRightA, minRightB);
                    return (maxLeft + minRight) / 2.0;
                } else {
                    // 如果牛群A和牛群B的总长度是奇数，直接返回中位数
                    maxLeft = max(maxLeftA, maxLeftB);
                    return maxLeft;
                }
            } else if (maxLeftA > minRightB) {
                // 如果分割线在牛群A的左侧，将分割线往左移
                right = i - 1;
            } else {
                // 如果分割线在牛群A的右侧，将分割线往右移
                left = i + 1;
            }
        }

        // 没有找到合适的分割线，返回 -1.0 表示没有中位数
        return -1.0;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！