用c++写一个分治法求众数

以下是一种实现方法：

#include <stdio.h>

// 用分治法求众数
int majority(int arr[], int left, int right) {
    if (left == right) { // 只有一个元素，直接返回该元素
        return arr[left];
    }

    int mid = (left + right) / 2; // 计算中间位置

    // 递归求左右两边的众数
    int left_majority = majority(arr, left, mid);
    int right_majority = majority(arr, mid+1, right);

    // 如果左右两边的众数相同，则直接返回该众数
    if (left_majority == right_majority) {
        return left_majority;
    }

    // 否则统计左右两边的众数出现的次数，返回出现次数较多的那个众数
    int left_count = 0;
    int right_count = 0;
    for (int i = left; i <= right; i++) {
        if (arr[i] == left_majority) {
            left_count++;
        } else if (arr[i] == right_majority) {
            right_count++;
        }
    }
    return left_count > right_count ? left_majority : right_majority;
}

int main() {
    int arr[] = {1, 1, 2, 2, 2, 3, 3, 3, 3, 3};
    int n = sizeof(arr) / sizeof(int);
    int majority_num = majority(arr, 0, n-1);
    printf("The majority number is: %d\n", majority_num);
    return 0;
}

该代码采用递归的方式实现分治法求众数，具体实现流程如下：

1. 若当前区间只有一个元素，则直接返回该元素。
2. 分治将当前区间分成左右两部分，分别递归求解左右两边的众数。
3. 若左右两边的众数相同，则直接返回该众数。
4. 否则统计左右两边的众数出现的次数，返回出现次数较多的众数。

该算法的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。