题解 | #三个牛群中位数#

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

1. 比较三个数组的长度，将长度最小的数组作为第二个数组参与比较，将长度最大的数组作为第三个数组参与比较。
2. 如果第一个数组为空，直接在第二个、第三个数组中查找第 k 小的元素。
3. 如果 k=1，直接返回三个数组中最小的元素。
4. 确定比较点 i、j、q，比较三个数组对应位置上的元素大小。
5. 如果 herd1[i] 最小，说明中位数在 herd1[i+1:]、herd2[l2:]、herd3[l3:] 这三个数组中，此时递归调用 find_k_minest_3 方法，在新的三个数组中查找第 k-(i+1-l1) 小的元素。
6. 如果 herd2[j] 最小，说明中位数在 herd1[l1:]、herd2[j+1:]、herd3[l3:] 这三个数组中，此时递归调用 find_k_minest_3 方法，在新的三个数组中查找第 k-(j+1-l2) 小的元素。
7. 如果 herd3[q] 最小，说明中位数在 herd1[l1:]、herd2[l2:]、herd3[q+1:] 这三个数组中，此时递归调用 find_k_minest_3 方法，在新的三个数组中查找第 k-(q+1-l3) 小的元素。

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param herd1 int整型一维数组
# @param herd2 int整型一维数组
# @param herd3 int整型一维数组
# @return double浮点型
#
class Solution:
    def findMedianSortedArray(
        self, herd1: List[int], herd2: List[int], herd3: List[int]
    ) -> float:
        n1, n2, n3 = len(herd1), len(herd2), len(herd3)
        left = (n1 + n2 + n3 - 1) // 2 + 1
        right = (n1 + n2 + n3) // 2 + 1
        return (
            self.find_k_minest_3(herd1, 0, n1, herd2, 0, n2, herd3, 0, n3, left)
            + self.find_k_minest_3(herd1, 0, n1, herd2, 0, n2, herd3, 0, n3, right)
        ) / 2.0

    def find_k_minest_3(self, herd1, l1, r1, herd2, l2, r2, herd3, l3, r3, k):
        len1, len2, len3 = r1 - l1, r2 - l2, r3 - l3
        if len2 < len1 and len2 <= len3:
            return self.find_k_minest_3(herd2, l2, r2, herd1, l1, r1, herd3, l3, r3, k)
        if len3 < len1:
            return self.find_k_minest_3(herd3, l3, r3, herd2, l2, r2, herd1, l1, r1, k)
        if l1 == r1:
            return self.find_k_minest(herd2, l2, r2, herd3, l3, r3, k)
        if k == 1:
            return min(herd1[l1], min(herd2[l2], herd3[l3]))
        i = l1 + min(len1, k // 2) - 1
        j = l2 + k // 2 - 1
        q = l3 + k // 2 - 1
        min_val = min(herd1[i], min(herd2[j], herd3[q]))
        if min_val == herd1[i]:
            return self.find_k_minest_3(
                herd1, i + 1, r1, herd2, l2, r2, herd3, l3, r3, k - (i + 1 - l1)
            )
        elif min_val == herd2[j]:
            return self.find_k_minest_3(
                herd1, l1, r1, herd2, j + 1, r2, herd3, l3, r3, k - (j + 1 - l2)
            )
        else:
            return self.find_k_minest_3(
                herd1, l1, r1, herd2, l2, r2, herd3, q + 1, r3, k - (q + 1 - l3)
            )

    def find_k_minest(self, nums1, l1, r1, nums2, l2, r2, k):
        len1, len2 = r1 - l1, r2 - l2
        if len1 > len2:
            return self.find_k_minest(nums2, l2, r2, nums1, l1, r1, k)
        if l1 == r1:
            return nums2[l2 + k - 1]
        if k == 1:
            return min(nums1[l1], nums2[l2])
        i = l1 + min(k // 2, len1) - 1
        j = l2 + k // 2 - 1
        if nums1[i] > nums2[j]:
            return self.find_k_minest(nums1, l1, r1, nums2, j + 1, r2, k - (j - l2 + 1))
        else:
            return self.find_k_minest(nums1, i + 1, r1, nums2, l2, r2, k - (i - l1 + 1))