• 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;
}

• 运行结果

1.众数问题：

给定含有N个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中重数最大的元素称为多重集合S的众数，众数的重数称为多重集合S的重数，试求一个给定多重结合的重数和众数。

例如：S={a,b,b,b,f,f,4,5}的重数是3，众数是b

2.算法思路：

• 首先为集合S排序，使之成为有序的数组（使用Arrays类的sort方法）
• 取中位数为众数，中位数的个数为重数，确定左右界
• 向左界递归，取中位数为众数，取中位数个数为重数，比较
• 向右界递归，取中位数为众数，取中位数个数为重数，比较

3.问题：

翻阅网上的代码，多是使用c++实现，而c++代码中有引用参数传递的过程，在程序运行中可以直接引用函数传参，但Java中没有提供。在阅读(7条消息) 分治法-众数问题java实现_cook_1996的博客-CSDN博客 这篇博客后，发现了IntHolder这个类。

IntHolder持有者类型：因为java中只存在值传递，同时包装类一旦创建其数值是不能改变的。所有不可能实现一个方法改变一个数据类型的值。如果想编写一个修改数据值参数的方法，就需要使用在 org.omg.CORBA 包中定义的持有者（holder）类型，包括IntHolder、BooleanHolder等。每个持有者类型都包含一个共有域值，通过它可以访问储存在其中的值。

4.代码：

import jdk.nashorn.internal.runtime.regexp.joni.encoding.IntHolder;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Mode {

    public static void getMaxCnt(int a[], int n, IntHolder num, IntHolder maxCnt){
        int l =0, r = 0;
        int s;
        int mid = n / 2;
        for( l = 0;l < mid;l ++){
            if(a[l] == a[mid])
                break;
        }
        for(r = mid + 1;r < n;r ++){
            if(a[r] != a[mid])
                break;
        }
        s = r - l;
        if(s > maxCnt.value){
            num.value = a[mid];
            maxCnt.value = s;
        }
        if(s == maxCnt.value){
            if(num.value > a[mid]){
                num.value = a[mid];
                maxCnt.value = s;
            }
        }
        if(l + 1 > maxCnt.value){
            getMaxCnt(a,l+1,num,maxCnt);
        }
        if(n - r > maxCnt.value){
            int [] b = new int[n-r];
            for(int i = 0;i < n-r;i ++){
                b[i] = a[r + i];
            }
            getMaxCnt(b,n-r,num,maxCnt);
        }

    }

    public static void main(String[] args) {
        int i,n;

        IntHolder num = new IntHolder();
         IntHolder maxCnt = new IntHolder();
        System.out.println("请输入数组个数：");
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int []a = new int[n];
        System.out.println("请输入一个数组：");
        for(i = 0;i < n;i ++){
            a[i] = scanner.nextInt();
        }
        Arrays.sort(a);
        getMaxCnt(a,n,num,maxCnt);
        System.out.println("众数：" + num.value + " 重数：" + maxCnt.value);
    }
}

众数问题
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;
}