Zzulioj:1201: mode problem

 

1201: The question of mode

The time limit : 1 Sec   Memory limit : 128 MB
Submit : 2504   solve : 1635
[ state ] [ Discussion board ] [ Submit ] [ Propositional person : External import ]

Title Description

Given to contain n Multiple sets of elements S, Each element in S The number of occurrences in is called the multiplicity of the element . Multiple sets S The element with the largest multiplicity is called mode .
for example ,S={1,2,2,2,3,5}. Multiple sets S What is the mode 2, Its multiplicity is 3.
Programming tasks ：
For a given by n A multiple set of natural numbers S, Programming calculation S Mode and multiplicity of .

Input

The first 1 Row multiset S The number of elements in n(n<=50000); Next n In line , Each line has a natural number .

Output

Output file has 2 That's ok , The first 1 OK, give me a few , The first 2 A row is a multiplicity .( If there are multiple modes , Output only the smallest )

The sample input  Copy

6
1
2
2
2
3
5

Sample output  Copy

2
3

source / classification

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct most {
    int num, fre;
}M;
M m[50001];
int max_ = -1;
static int flag = 0;
void quicksort(int l, int r) {// Quick line up , Find the maximum value by the way 
    int p = l;
    if (l < r) {
        int index = p + 1;
        for (int i = index; i <= r; i++) {
            if(flag == 0) // Find the maximum value in the first call , Prevent wasting time 
                max_ = max(max_, m[i].fre);
            if (m[i].num < m[p].num) {
                M t = m[i];
                m[i] = m[index];
                m[index] = t;
                index++;
            }
        }
        M t = m[p];
        m[p] = m[index - 1];
        m[index - 1] = t;
        flag++;
        quicksort(l, p - 1);
        quicksort(p + 1, r);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int low, t, sum = 0;
    for (int i = 0; i < n; i++) {// save 
        t = 0;
        cin >> low;
        for (int j = 0; j < sum; j++) {
            if (m[j].num == low) {
                m[j].fre++;
                t = 1;
                break;
            }
        }
        if (t == 0) { 
            m[sum].num = low;
            m[sum].fre++;
            sum++;
        }
    }
    quicksort(0, sum - 1);// Sort 
    for (int i = 0; i < sum; i++) {
        if (m[i].fre == max_) {// If the maximum value is found , Prove that you found that number 
            cout << m[i].num << '\n' << m[i].fre;
            break;
        }
    }
    return 0;
}