python分治法求众数

你好，使用分治法求一个列表中的众数可以采用 Boyer-Moore 投票算法，思路如下：

1. 遍历列表中的每一个元素；
2. 如果当前元素与所记录的候选众数相同，则将计数器加一；
3. 如果当前元素与所记录的候选众数不同，则将计数器减一；
4. 如果计数器减到了 0，则需要更换候选众数，将当前元素作为新的候选众数；
5. 遍历完整个列表后，所记录的候选众数就是该列表的众数。

示例代码如下：

def majority_element(nums):
    """
    分治法求众数
    :param nums: 列表
    :return: 众数
    """
    # 候选众数
    candidate = None
    # 候选众数出现的次数
    count = 0

    # 遍历列表中的每一个元素
    for num in nums:
        # 如果计数器为 0，则需要更换候选众数
        if count == 0:
            candidate = num
            count = 1
        # 如果当前元素与所记录的候选众数相同，则将计数器加一
        elif num == candidate:
            count += 1
        # 如果当前元素与所记录的候选众数不同，则将计数器减一
        else:
            count -= 1

    return candidate

然后我们来测试一下：

nums = [1, 2, 3, 3, 4, 5, 5, 5]
print(f"列表 {nums} 中的众数为：{majority_element(nums)}")

输出结果为：

列表 [1, 2, 3, 3, 4, 5, 5, 5] 中的众数为：5

注意：如果列表中没有众数，则该算法并不适用。