【CSP201312-1 】出现次数最多的数，排序后扫描并记录

problem

问题描述
　　给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。
输入格式
　　输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。
　　输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
输出格式
　　输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
样例输入
6
10 1 10 20 30 20
样例输出
10

solution

真的经典题了，做法有好多的样子qaq
我最早是在啊哈算法的后传里看到的，msra的面试题。

做法1
直接桶排统计，然后扫一遍统计出现次数最多的，复杂度是O（X），X为最大数。

#include<iostream>
using namespace std;
int a[10010];
int main(){
  int n;  cin>>n;
  for(int i = 1; i <= n; i++){
    int x;  cin>>x;  a[x]++;
  }
  int ans = 0, max = 0;
  for(int i = 1; i <= 10010; i++){
    if(a[i]>max){
      ans = i; max = a[i];
    }
  }
  cout<<ans<<'\n';
  return 0;
}

做法2
可以排序，排完后相同元素都会聚在一起，然后扫一遍用个变量记录出现次数最多的即可，快排复杂度O(nlogn)

#include<iostream>
#include<algorithm>
using namespace std;
int a[1010];
int main(){
  int n;  cin>>n;
  for(int i = 1; i <= n; i++)cin>>a[i];
  sort(a+1,a+n+1);
  int ans = 0, max = 0, count=1;
  for(int i = 2; i <= n; i++){
    if(a[i]==a[i-1])count++;
    else{
      if(count>max){
        max = count;
        ans = a[i-1];
      }
      count = 1;
    }
  }
  if(count>max){
    max = count;
    ans = a[n];
  }
  cout<<ans<<endl;
  return 0;
}