C语言 众数问题 分治法
解题思路：

①排序：拿到一个乱序的数列，先排序（顺序跳过这一步）

②找中位数

③ 遍历：得到与中位数相等的第一个数与最后一个数的位置

④比较：（当前和中位数相等的数的个数）和（重数的大小）大于——>更新众数与重数

⑤分治：

左边非中位数的个数>一坨中位数的个数 ——>众数有可能在左边

右边非中位数的个数<一坨中位数的个数 ——>众数有可能在右边
代码实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int mode = 0;//众数
int multiplicity  = 0;//重数

void FindMode(int n[],int low, int high)
{
    //找到中位数
    int mid = n[(low+high)/2];

    //与中位数相等的第一个数与最后一个数的位置
    int first = 0,last =  0;
    for(int i=low;i<high;i++)
    {
        if(n[i] == mid)
        {
            first = i;
            break;
        }
    }
    for(int i = first;i<high;i++)
    {
        if(n[i] != mid)
        {
            last = i;
            break;
        }
    }

    if(multiplicity<last-first+1)
    {
        multiplicity = last-first+1;
        mode = mid;
    }

    if(first+1>last-first+1)
    {
        FindMode(n,low,first);
    }

    if(high-last+1>last-first+1)
    {
        FindMode(n,last,high);
    }
}

void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j)
        {
            while(i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
            {
                j--;
            }

            if(i < j)
            {
                arr[i++] = arr[j];
            }

            while(i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
            {
                i++;
            }

            if(i < j)
            {
                arr[j--] = arr[i];
            }
        }

        arr[i] = k;

        // 递归调用
        QuickSort(arr, low, i - 1);     // 排序k左边
        QuickSort(arr, i + 1, high);    // 排序k右边
    }
}

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

    //快速排序
    QuickSort(a, 0, n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    FindMode(a, 0, n-1);
    printf("众数为：%d",mode);
    return 0;
}

疑惑：如果有多个众数怎么办？
（有问题烦请批评指证）

Problem Description


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

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

Output

输出数据的第1行给出众数，第2行是重数。
Sample Input
6
1
2
2
2
3
5

Sample Output
2
3



问题解读



该问题就是求一个集合最小众数的问题。



代码实现


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int mode;   //众数
    int Max=INT_MIN;   //众数的重数，因为要求最大值，故初始化为最小值
    int times[10000000];   //用于记录多重集合S中每个元素出现的次数。注意：多重集S中可能只有一个元素，因此该元素的重数为 n
    cin>>n;
    while(n--)
    {
        int x;   //多重集合S中的元素
        cin>>x;
        times[x]++;   //元素 x 的出现次数加一
        if(Max<times[x])   //如果当前众数的重数小于元素 x 的出现次数，说明 x 为众数
        {
            mode=x;   //更新众数
            Max=times[x];   //更新众数的重数
        }
        else if(Max==times[x])   //如果当前众数的重数等于元素 x 的出现次数，说明两个数都是众数，这时需要选出最小的那个
        {
            if(x<mode)
                mode=x;
        }
    }
    cout<<mode<<endl<<Max<<endl;
    return 0;
}



运行结果

众数问题

Time Limit: 2000 ms Memory Limit: 65536 KiB
Problem Description

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

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

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

6

1

2

2

2

3

5

Sample Output

2

3

Hint

Source
这个题，我的算法思想就是排序，然后找出数组最中间的那个数来，然后用for循环向左向右找和这个数相同的，用变量cnt进行计数，看看有多少个，如果不相同，退出循环，并保存左边和右边的下标i，j。此时，判断左边剩余的元素个数是否大于现在众数的重数，如果大，则继续递归，右边同理。
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int maxsum,zhongshu,n;

void zhong(int a[],int l,int r)
{
    int center = (l + r) / 2;
    int i,j;
    int cnt = 1;
    for(i = center-1; i >= l ; i--)
    {
        if(a[i] == a[center])
        {
            cnt++;
        }
        else
            break;
    }
    for(j = center+1; j <= r; j++)
    {
        if(a[j] == a[center])
            cnt++;
        else
            break;
    }
    if(cnt == maxsum && zhongshu > a[center])      //若相等，则元素小的优先
    {
        maxsum = cnt;
        zhongshu = a[center];
    }
    if(cnt > maxsum)
    {
        maxsum = cnt;
        zhongshu = a[center];
    }
    if(i-l > maxsum)      //若左边剩余元素还大于重数，则有可能会存在更大的众数重数，递归寻找
    {
        zhong(a,l,i);
    }
    if(r-j > maxsum)     //右边同理
        zhong(a,j,r);


}

int main()
{
    cin>>n;
    int a[n+9];
    for(int i = 0; i < n; i++)
        cin>>a[i];
    maxsum = zhongshu = 0;
    sort(a,a+n);
    zhong(a,0,n-1);
    cout<<zhongshu<<endl;
    cout<<maxsum<<endl;
}

一：题目

给定含有n个元素的多重集合s，每个元素在s中出现的次数称为该元素的重数，多重集s中重数最大的元素称为众数，给定多重集合s，求s中的众数集重数。

二：思路

首先，我们最容易想到的就是统计每个数的出现次数，然后比较得出结果。这个思路可以利用容器来实现。

仔细思考，这道题目还可以用分治法来解决。

解决步骤：

①给数组排序；

②找出中位数v并且确定中位数的个数num和左右边界；

③如果左边界左边数字的个数比num大，说明众数可能在左边，重复②之后的步骤；

④如果右边界右边数字的个数比num大，说明众数可能在右边，重复②之后的步骤；

⑤得出众数v和重数num。

三：代码

public class solution {
    public static final int maxn = 10000;
    public static int[] a = new int[maxn];
    public static int num, v;

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        System.out.println("请输入数组长度（<=10000）：");
        int n = cin.nextInt();
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            a[i] = (rand.nextInt(100) + 1) % 20;
        }
        Arrays.sort(a, 0, n);
        for(int i = 0; i < n; i++) {
            System.out.println(a[i]);
        }
        solve(0, n - 1);
        System.out.println("Value:" + v);
        System.out.println("Number:" + num);
    }

    public static void solve(int l, int r) {
        if (l > r)
            return;
        int mid = (l + r) / 2;
        int i = mid, j = mid;
        while (i >= 0 && a[i] == a[mid])
            i--;
        while (a[j] == a[mid] && j <= a.length - 1)
            j++;
        if (j - i - 1 > num) {
            num = j - i - 1;
            v = a[mid];
        }
        if (i - l + 1 > num) {
            solve(l, i);
        }
        if (r - j + 1 > num) {
            solve(j, r);
        }
    }
}