Python实现分治法求众数

以下是Python实现分治法求众数的代码和解释：

def majority_element(nums):
    """
    分治法求众数
    """
    def majority_element_rec(lo, hi):
        # 递归终止条件
        if lo == hi:
            return nums[lo]

        # 分治
        mid = (hi - lo) // 2 + lo
        left = majority_element_rec(lo, mid)
        right = majority_element_rec(mid + 1, hi)

        # 合并
        if left == right:
            return left
        left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
        right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)
        return left if left_count > right_count else right

    return majority_element_rec(0, len(nums) - 1)

解释：

该算法的思路是将数组分成左右两个部分，分别求出左右两个部分的众数，然后再将左右两个部分的众数合并，最终得到整个数组的众数。

具体实现时，我们可以使用递归的方式，将数组不断分成左右两个部分，直到数组的大小为1，此时返回该元素。然后将左右两个部分的众数合并，如果左右两个部分的众数相同，则直接返回该众数；否则，统计左右两个部分中各自众数的出现次数，返回出现次数较多的众数。