Java 题解 | #牛的体重排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weightsA int整型一维数组
     * @param weightsB int整型一维数组
     * @return double浮点型
     */
    public double findMedianSortedArrays (int[] weightsA, int[] weightsB) {
        // write code here
        int m = weightsA.length;
        int n = weightsB.length;
        if (m > n) {
            int[] temp = weightsA;
            weightsA = weightsB;
            weightsB = temp;
            int tempLen = m;
            m = n;
            n = tempLen;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && weightsB[j - 1] > weightsA[i]) {
                iMin = i + 1;
            } else if (i > iMin && weightsA[i - 1] > weightsB[j]) {
                iMax = i - 1;
            } else {
                int maxOfLeft, minOfRight;
                if (i == 0) maxOfLeft = weightsB[j - 1];
                else if (j == 0) maxOfLeft = weightsA[i - 1];
                else maxOfLeft = Math.max(weightsA[i - 1], weightsB[j - 1]);

                if ((m + n) % 2 == 1) return maxOfLeft;

                if (i == m) minOfRight = weightsB[j];
                else if (j == n) minOfRight = weightsA[i];
                else minOfRight = Math.min(weightsA[i], weightsB[j]);

                return (maxOfLeft + minOfRight) / 2.0;
            }
        }
        return 0;
    }
}

该代码使用的编程语言是Java

这道题考察的是在两个有序数组中找到中位数的问题。给定两个有序数组weightsA和weightsB，要求计算这两个数组的合并数组的中位数。

解决思路是使用二分查找的方法。首先需要对数组进行预处理，使得较短的数组为weightsA，较长的数组为weightsB。然后使用二分查找的方式在weightsA数组中选择一个下标i，在weightsB数组中选择一个下标j，使得：

1. i + j == (m + n + 1) / 2，其中m和n分别是weightsA和weightsB的长度；
2. weightsA[i - 1] <= weightsB[j]且weightsB[j - 1] <= weightsA[i]，即两个数组中的元素满足左侧的元素都小于右侧的元素。

根据上述条件，可以找到中位数。如果数组的总长度为奇数，则中位数为maxOfLeft；如果数组的总长度为偶数，则中位数为(maxOfLeft + minOfRight) / 2.0。