用分治法求众数和重数python

分治法通常用于解决复杂问题，如寻找数组中的众数（最常见的元素）。在Python中，我们可以结合分治策略和哈希集合数据结构来实现这个算法。这里有一个简单的思路：

1. **合并过程**（Merge）：将两个已经排好序的小规模数组合并成一个大数组，并更新众数信息。这一步是递归的基础。

2. **分解过程**（Divide）：将原始数组拆分为两部分，如果数组长度大于1，则继续对每一部分递归地寻找众数。

3. **查找过程**（Search）：对于小规模数组，遍历即可找出众数。因为数组已排序，所以只需找到第一个和最后一个相同的元素即可。

下面是一个基于上述思想的 Python 函数示例：

def find_mode(arr):
    if len(arr) == 1:
        return arr[0], 1

    # Divide the array into two halves
    mid = len(arr) // 2
    left_half, right_half = arr[:mid], arr[mid:]

    # Find mode in each half recursively
    left_mode, left_count = find_mode(left_half)
    right_mode, right_count = find_mode(right_half)

    # Merge and compare counts to find overall mode
    common_count = min(left_count, right_count)
    left_common = left_mode == right_mode
    if left_common and left_count > common_count:
        return left_mode, left_count + right_count
    elif right_common and right_count > common_count:
        return right_mode, left_count + right_count
    else:
        # If no common mode found, check if any element appears only once in both halves
        left_only_once, right_only_once = False, False
        if left_count == 1 and right_mode not in left_half:
            left_only_once = True
        if right_count == 1 and left_mode not in right_half:
            right_only_once = True

        if left_only_once and right_only_once:
            return max(left_mode, right_mode), 1
        else:
            return None, 0  # No unique mode found

# 示例
arr = [1, 1, 2, 2, 2, 3]
mode, count = find_mode(arr)
print(f"众数是 {mode}，出现了 {count} 次.")