题解 | #牛的体重排序#

• 题目考察的知识点 : 二分，分而治之
• 题目解答方法的文字分析：

1. 首先找出两个牛群各自的中位数，分别为nums1[i-1]和nums2[j-1]。然后根据中位数的定义比较nums1[i-1]和nums2[j]以及nums2[j-1]和nums1[i]的大小关系。
2. 如果nums1[i-1]大于nums2[j]，则说明中位数位于nums1[0:i-1]和nums2[j:n]之间，可以将搜索范围缩小到[imin, i-1]区间内继续查找；
3. 如果nums2[j-1]大于nums1[i]，则说明中位数位于nums1[i:m]和nums2[0:j-1]之间，因此我们将搜索范围缩小到[i+1, imax]区间内继续查找；
4. 否则，a和b就是中位数，返回(a+b)/2即可

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param weightsA int整型一维数组
# @param weightsB int整型一维数组
# @return double浮点型
#
class Solution:
    def findMedianSortedArrays(self, weightsA: List[int], weightsB: List[int]) -> float:
        m, n = len(weightsA), len(weightsB)
        if m > n:
            weightsA, weightsB, m, n = weightsB, weightsA, n, m
        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if j > 0 and i < m and weightsB[j-1] > weightsA[i]:
                imin = i + 1
            elif i > 0 and weightsA[i-1] > weightsB[j]:
                imax = i - 1
            else:
                if i == 0: max_of_left = weightsB[j-1]
                elif j == 0: max_of_left = weightsA[i-1]
                else: max_of_left = max(weightsA[i-1], weightsB[j-1])
                if (m + n) % 2 == 1:
                    return max_of_left
                if i == m: min_of_right = weightsB[j]
                elif j == n: min_of_right = weightsA[i]
                else: min_of_right = min(weightsA[i], weightsB[j])
                return (max_of_left + min_of_right) / 2.0