题解 | #牛的体重排序#

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) % 2 == 0) {
            return (findKthElement(weightsA, weightsB,
                                   (m + n) / 2) + findKthElement(weightsA, weightsB,
                                           (m + n) / 2 + 1)) / 2.0;
        } else {
            return findKthElement(weightsA, weightsB, (m + n) / 2 + 1);
        }
    }

    private int findKthElement(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int newIndex1 = Math.min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = Math.min(index2 + k / 2 - 1, n - 1);

            if (nums1[newIndex1] <= nums2[newIndex2]) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
}

考察的知识点：

1. 二分查找：利用二分查找的思想在有序数组中查找第 k 小的元素。
2. 数组操作：在有序数组中查找元素并更新指针。
3. 数学处理：根据奇偶情况返回中位数。

解题思路:

假设 m <= n，我们从两个有序数组的中间分别取两个下标：A_mid = m / 2 和 B_mid = (m + n) / 2 - m / 2。如果 A[A_mid] < B[B_mid]，那么说明中位数位于 A[A_mid] 的右边或者 B[B_mid] 的左边，我们可以排除掉 A 数组中的前 A_mid 个元素。反之，如果 A[A_mid] > B[B_mid]，则可以排除掉 B 数组中的前 B_mid 个元素。

每次排除掉一部分元素后，我们可以更新 k，然后继续在更新后的数组中查找第 k 小的元素。直到 k 减小到 1，此时我们就找到了中位数。