题解 | #牛的体重排序#

考察的知识点：数组、二分查找；

解答方法分析：

1. 获取 weightsA 和 weightsB 的长度，分别用 m 和 n 表示。
2. 如果 m 大于 n，则交换 weightsA 和 weightsB，以确保 weightsA 是较短的数组。
3. 定义左边界 left 和右边界 right，初始化为 0 和 m，用于进行二分查找。
4. 定义 halfLen，并计算出中位数需要划分两个数组的位置：halfLen = (m + n + 1) / 2。
5. 进入二分查找循环，循环条件是 left 小于等于 right。
6. 在每次循环中，计算出划分位置 i 和 j：i = (left + right) / 2，j = halfLen - i。
7. 判断 weightsB[j-1]和 weightsA[i] 的关系：如果 weightsB[j-1] 大于 weightsA[i]，说明 i 需要右移，更新 left = i + 1。如果 weightsA[i-1] 大于 weightsB[j]，说明 i 需要左移，更新 right = i - 1。否则，找到了合适的划分位置，继续下一步操作。
8. 计算左半部分的最大值 maxLeft 和右半部分的最小值 minRight：如果 i = 0，maxLeft = weightsB[j - 1]。如果 j = 0，maxLeft = weightsA[i - 1]。否则，maxLeft = max(weightsA[i - 1], weightsB[j - 1])。如果 (m + n) 为奇数，直接返回 maxLeft，作为中位数。如果 i = m，minRight = weightsB[j]。如果 j = n，minRight = weightsA[i]。否则，minRight = min(weightsA[i], weightsB[j])。
9. 如果 (m + n) 为偶数，返回 (maxLeft + minRight) / 2.0 作为中位数。
10. 循环结束后仍未找到合适的划分位置，返回默认值 0.0。

所用编程语言：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();

        if (m > n) {
            swap(weightsA, weightsB);
            swap(m, n);
        }

        int left = 0;
        int right = m;
        int halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = halfLen - i;

            if (i < right && weightsB[j - 1] > weightsA[i]) {
                left = i + 1;
            } else if (i > left && weightsA[i - 1] > weightsB[j]) {
                right = i - 1;
            } else {
                int maxLeft = 0, minRight = 0;
                if (i == 0) {
                    maxLeft = weightsB[j - 1];
                } else if (j == 0) {
                    maxLeft = weightsA[i - 1];
                } else {
                    maxLeft = max(weightsA[i - 1], weightsB[j - 1]);
                }

                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                if (i == m) {
                    minRight = weightsB[j];
                } else if (j == n) {
                    minRight = weightsA[i];
                } else {
                    minRight = min(weightsA[i], weightsB[j]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }

        return 0.0;
    }
};