题目描述

给定 n 个正整数，找出它们中出现次数最多的数。

如果这样的数有多个，请输出其中最小的一个。

输入格式
输入的第一行只有一个正整数 n，表示数字的个数。

输入的第二行有 n 个整数 s1,s2,…,sn。

相邻的数用空格分隔。

输出格式
输出这 n 个次数中出现次数最多的数。

如果这样的数有多个，输出其中最小的一个。

数据范围
1≤n≤1000,
1≤si≤10000

样例

输入：
6
10 1 10 20 30 20
输出：
10

我的小白思路

第一步：排序
第二步：创造一个数组，比如1 1 3 4 5 6 6 6 7一组数，数组里记录[1,2,3,4,7,8]，即前一个数字要是不同于后一个数的话，把前一个数字位置记录下来
第三步：查找数组中差值a[i+1]-a[i]（相同的值）最大的，并记录下a[i]的值
第四步：通过a[i]的值可以找到原值，输出

时间复杂度O(nlog(n))

C++ 代码

#include <iostream>
#include <algorithm>
const int N = 1010;
int num[N];
int n;
int locate;
int temp = 0;
using namespace std;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)   cin >> num[i];
    sort(num, num + n);

    int sort[n+10];
    int j = 0;
    for(int i = 1; i <= n; i++)
    {
        if(num[i-1] != num[i])
                {
            sort[j] = i-1;
            j++;
        }
    }

    for(int i = 0; i < j-1; i++)
    {
        if(sort[i + 1] - sort[i] > temp)
        {
            temp = sort[i + 1] - sort[i];
            locate = sort[i];
        }
    }

    cout << num[locate + 1] << endl;
    return 0;
}

y总做法

哈希表

时间复杂度O（n）

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;

int n;
int s[N];

int main()
{
    cin >> n; // 数据量小于100000时，cin和scanf都可以，大于十万时，scanf效率更高
    while( n-- )
    {
        int x;
        cin >> x;
        s[x] ++;
    }

    int res = 0;
    for(int i = 0; i < N; i++)
        if(s[i] > s[res])
            res = i;

    cout << res << endl;
    return 0;
}