问题描述
给定含有 n 个元素的多重集合 S，每个元素在 S 中出现的次数称为该元素的重数。多重集合 S 中重数最大的元素称为众数。例如，S={1, 2, 2, 2, 3, 5}，多重集合 S 的众数是 2，其重数为 3。

算法设计
对于给定的由 n 个自然数组成的多重集 S，计算 S 的众数及其重数。

数据输入
输入数据由文件名为 input.txt 的文本文件提供。文件的第 1 行为多重集 S 中元素个数 n；在接下来的 n 行中，每行有一个自然数。

结果输出
将计算结果输出到文件 output.txt。输出文件有 2 行，第 1 行是众数，第 2 行是重数。

input

output

2  3

#include <iostream>
#include <algorithm>
#define MAXN 1000010
int n;//数据个数
int a[MAXN];//数据数组
int element;//众数
int count = 0;//重数
//method 1: sort and partition
void partition(int l, int r) {
    int med = a[(l + r) / 2];//中位数
    int count_temp = 0;
    int l1, r1;//左边半截
    l1 = l;
    int l2, r2;//右边半截
    r2 = r;
    for (int i = l; i <= r; i++) {
        if (a[i] == med) {
            r1 = i - 1;
            break;
        }
    }
    for (int i = r; i >= l; i--) {
        if (a[i] == med) {
            l2 = i + 1;
            break;
        }
    }
    for (int i = l; i <= r; i++) {
        if (a[i] == med)
            count_temp++;
    }
    if (count_temp > count) {//更新众数和重数
        count = count_temp;
        element = med;
    }
    int left_count = r1 - l1 + 1;//左半截数量
    int right_count = r2 - l2 + 1;//右半截数量
    if (left_count > count_temp) {//左半截数量大于中位数数量，说明左半截可能出现众数
        partition(l, r1);
    }
    if (right_count > count_temp) {//右半截数量大于中位数数量，说明右半截可能出现众数
        partition(l2, r);
    }
}
//method 2: no sort
int partition_without_sort(int l, int r) {//类似于快排的思想，将数组分为三部分，比基准小，比基准大，和基准
    int pivot = a[l];//选取第一个元素作为基准
    int i = l;
    int j = r;
    int count_temp = 1;//基准本身也算一次
    while (i < j) {
        while (i < j && a[j] >= pivot) {
            if (a[j] == pivot) count_temp++;
            j--;//从右往左找到第一个小于基准的元素
        }
        a[i] = a[j];//将小于基准的元素放到左边
        while (i < j && a[i] <= pivot) {
            if (a[i] == pivot) count_temp++;
            i++;//从左往右找到第一个大于基准的元素
        }
        a[j] = a[i];//将大于基准的元素放到右边
    }
    a[i] = pivot;//将基准放到中间
    if (count_temp > count) {//更新众数和重数
        count = count_temp;
        element = pivot;
    }
    return i;//返回基准的位置，作为分割点
}

void getElement(int l, int r) {
    int mid = partition_without_sort(l, r);
    int l1=l,r1=mid-1,l2=mid+1,r2=r;
    int left_count = r1 - l1 + 1;
    int right_count = r2 - l2 + 1;
    if (left_count > count) {//如果左半截数量大于众数数量，说明左半截可能出现众数
        getElement(l, mid - 1);
    }
    if (right_count > count) {//如果右半截数量大于众数数量，说明右半截可能出现众数
        getElement(mid + 1, r);
    }
}


int main() {
    std::cin >> n;
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
    //method 1: sort and partition
    // std::sort(a, a + n);//排序,O(nlogn)
    // partition(0, n - 1);
    // std::cout << element << " " << count << std::endl;
    //method 2: no sort，，不排序也能做，但感觉没必要，复杂度一样的
    getElement(0, n - 1);
    std::cout << element << " " << count << std::endl;

}

/*
6
1 2 2 2 3 4
10
3 1 4 5 2 3 2 5 6 3
*/