用分治法C语言求解众数问题

以下是用分治法求解众数问题的C语言代码：

#include <stdio.h>

// 求解子数组的众数
int majority(int* nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    // 分治求解左右子数组的众数
    int mid = left + (right - left) / 2;
    int leftMajority = majority(nums, left, mid);
    int rightMajority = majority(nums, mid + 1, right);

    // 如果左右众数相同，直接返回
    if (leftMajority == rightMajority) {
        return leftMajority;
    }

    // 统计左右众数出现的次数
    int leftCount = 0, rightCount = 0;
    for (int i = left; i <= right; i++) {
        if (nums[i] == leftMajority) {
            leftCount++;
        } else if (nums[i] == rightMajority) {
            rightCount++;
        }
    }

    // 返回出现次数较多的众数
    return leftCount > rightCount ? leftMajority : rightMajority;
}

int main() {
    int nums[] = {1, 2, 2, 3, 2, 4, 2, 5, 2};
    int n = sizeof(nums) / sizeof(int);

    int result = majority(nums, 0, n - 1);

    printf("The majority element is %d\n", result);

    return 0;
}

该算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)。其中，n为数组的长度。