分治算法求解众数问题：C语言代码实现

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1, 2, 2, 2, 3, 5}。多重集S的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。如果出现多个众数，请输出最小的那个。

输入

输入数据的第1行是多重集S中元素个数n（n<1300000）；接下来的n行中，每行有一个最多含有5位数字的自然数。

输出

输出数据的第1行给出众数，第2行是重数。

分治算法解决问题

分治算法的基本思想是将一个大问题分解为若干个子问题，然后递归地解决这些子问题，并将子问题的解合并起来得到原问题的解。

在这个问题中，我们可以将多重集S分成两部分，分别求出每个子集的众数及其重数，然后再将两个子集的众数及其重数进行比较，得到整个多重集的众数及其重数。

具体的分治算法解决众数问题的步骤如下：

如果多重集S中只有一个元素，那么这个元素就是众数，重数为1。
如果多重集S中有多个元素，将S分成两部分，分别为S1和S2。
分别求出S1和S2的众数及其重数，分别为mode1和count1、mode2和count2。
如果mode1等于mode2，那么整个多重集的众数就是mode1，重数为count1 + count2。
如果mode1不等于mode2，那么比较count1和count2的大小，较大的作为整个多重集的众数，重数为较大的count值。

C语言代码实现

#include <stdio.h>

// 分治算法求众数及其重数
void majority(int S[], int n, int *mode, int *count) {
    // 多重集只有一个元素
    if (n == 1) {
        *mode = S[0];
        *count = 1;
        return;
    }

    // 多重集分成两部分
    int mid = n / 2;
    int *S1 = S;
    int *S2 = S + mid;

    int mode1, count1, mode2, count2;
    // 分别求出S1和S2的众数及其重数
    majority(S1, mid, &mode1, &count1);
    majority(S2, n - mid, &mode2, &count2);

    // 比较mode1和mode2
    if (mode1 == mode2) {
        *mode = mode1;
        *count = count1 + count2;
    } else {
        *mode = (count1 > count2) ? mode1 : mode2;
        *count = (count1 > count2) ? count1 : count2;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int S[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &S[i]);
    }

    int mode, count;
    majority(S, n, &mode, &count);

    printf("%d\n", mode);
    printf("%d\n", count);

    return 0;
}

代码解析

代码中，majority函数递归地求解多重集的众数及其重数。函数的输入参数为多重集数组S，多重集大小n，以及两个指针mode和count，用于存储计算得到的众数和重数。

在majority函数中，首先判断多重集是否只有一个元素，如果是，则直接将该元素赋值给mode，并将重数赋值为1。否则，将多重集分成两个子集，分别递归调用majority函数求解子集的众数及其重数。

最后，比较两个子集的众数，如果相同，则合并其重数；否则，取重数较大的子集的众数作为整个多重集的众数。

总结

本文介绍了使用分治算法求解众数问题，并提供了完整的C语言代码实现。代码简洁易懂，并附带详细的解析，方便读者理解和学习。分治算法是一种非常常用的算法思想，可以有效地解决许多复杂问题。