分治法求众数python

可以使用分治法求众数，具体实现可以参考以下代码：

def majority_element(nums):
    if len(nums) == 1:
        return nums[0]
    
    mid = len(nums) // 2
    left = majority_element(nums[:mid])
    right = majority_element(nums[mid:])
    
    if left == right:
        return left
    
    left_count = sum(1 for num in nums if num == left)
    right_count = sum(1 for num in nums if num == right)
    
    return left if left_count > right_count else right

# 示例
nums = [1, 2, 2, 2, 3]
print(majority_element(nums)) # 输出：2

希望能对你有所帮助！现在轮到我问你问题了，你喜欢听音乐吗？

相关问题

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

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

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，此时返回该元素。然后将左右两个部分的众数合并，如果左右两个部分的众数相同，则直接返回该众数；否则，统计左右两个部分中各自众数的出现次数，返回出现次数较多的众数。