题解 | #牛的体重排序#

一、知识点：

二分查找

二、文字分析：

首先，假设合并后的数组总共有 (m+n) 个元素，其中 m 和 n 分别是牛群 A 和牛群 B 的牛的数量。

如果 (m+n) 是奇数，中位数就是合并后数组的第 ((m+n)/2 + 1) 个元素；

如果 (m+n) 是偶数，中位数就是合并后数组的第 ((m+n)/2) 个元素和第 ((m+n)/2 + 1) 个元素的平均值。

为了达到时间复杂度 O(log (m+n))，我们可以使用二分查找。

在每一次迭代中，我们都要在牛群 A 和牛群 B 的体重数组中各自选取一个位置（假设选取的位置为 i 和 j），将两个子数组分割成四个部分：

leftA | rightA

A[0], A[1], …, A[i-1] | A[i], A[i+1], …, A[m-1]

leftB | rightB

B[0], B[1], …, B[j-1] | B[j], B[j+1], …, B[n-1]

我们需要满足以下两个条件：

1. len(leftA) + len(leftB) = len(rightA) + len(rightB)，即左侧部分的长度等于右侧部分的长度。
2. max(leftA) ≤ min(rightB) 且 max(leftB) ≤ min(rightA)，即左侧部分的最大值小于等于右侧部分的最小值。

当满足上述两个条件时，我们就找到了合适的位置 i 和 j，并可以计算出中位数。

三、编程语言：

java

四、正确代码：

public class Solution {
    public double findMedianSortedArrays(int[] weightsA, int[] weightsB) {
        int m = weightsA.length;
        int n = weightsB.length;

        if (m > n) {
            // 保证 m ≤ n
            int[] temp = weightsA;
            weightsA = weightsB;
            weightsB = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }

        int iMin = 0, iMax = m;
        int halfLen = (m + n + 1) / 2;

        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;

            if (i < m && weightsB[j - 1] > weightsA[i]) {
                // i 太小，增大 i
                iMin = i + 1;
            } else if (i > 0 && weightsA[i - 1] > weightsB[j]) {
                // i 太大，减小 i
                iMax = i - 1;
            } else {
                // i 是合适的位置
                int maxLeft;
                if (i == 0) {
                    maxLeft = weightsB[j - 1];
                } else if (j == 0) {
                    maxLeft = weightsA[i - 1];
                } else {
                    maxLeft = Math.max(weightsA[i - 1], weightsB[j - 1]);
                }

                if ((m + n) % 2 == 1) {
                    // 如果 (m + n) 是奇数，中位数就是 maxLeft
                    return maxLeft;
                }

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

                // 如果 (m + n) 是偶数，中位数就是 (maxLeft + minRight) / 2
                return (maxLeft + minRight) / 2.0;
            }
        }

        return 0.0;
    }
}