题解 | #牛的体重排序# 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，要求找到这两个数组合并后的中位数。

代码的文字解释如下：

1. 如果m大于n，则交换weightsA和weightsB的值，以及m和n的值，保证weightsA的长度始终小于等于weightsB的长度。
2. 初始化指针变量iMin、iMax和halfLen。iMin表示weightsA数组的最小索引，iMax表示weightsA数组的最大索引，halfLen表示整个合并数组的一半长度。
3. 使用二分查找的方法，在weightsA数组中进行查找，使得i的值满足以下条件：i + j = halfLen，其中j = (m + n + 1) / 2 - iweightsB[j-1] <= weightsA[i]（weightsB的左边最大值小于或等于weightsA的右边最小值）weightsA[i-1] <= weightsB[j]（weightsA的左边最大值小于或等于weightsB的右边最小值）
4. 根据二分查找得到的i值进行判断：如果i=0，说明weightsA的全部元素都在合并数组的右边，此时合并数组的左边最大值为weightsB[j-1]；如果j=0，说明weightsB的全部元素都在合并数组的右边，此时合并数组的左边最大值为weightsA[i-1]；否则，合并数组的左边最大值为max(weightsA[i-1], weightsB[j-1])。
5. 判断合并后的数组长度是否为奇数，如果是，则直接返回合并数组的左边最大值作为中位数。
6. 如果i=m，说明weightsA的全部元素都在合并数组的左边，此时合并数组的右边最小值为weightsB[j]； 如果j=n，说明weightsB的全部元素都在合并数组的左边，此时合并数组的右边最小值为weightsA[i]； 否则，合并数组的右边最小值为min(weightsA[i], weightsB[j])。
7. 计算合并数组的左边最大值和右边最小值的平均值，并返回作为中位数。