Problem 1582 众数问题

Accept: 740 Submit: 3690 Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

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

例如，S={1，2，2，2，3，5}。

多重集S的众数是2，其重数为3。

Input

输入包括多组数据，请处理到EOF结束。

每组数据，以一个n(1<=n<=100,000)开始，接下n行，每行有一个数字(-231~231)。

Output

对于每组输入数据，输出一行一个数字，表示众数。如果存在多个解，只需输出值最小的众数即可。

Sample Input

6 1 2 2 2 3 5 3 -1 -1 -1

Sample Output

2

-1

Source

FOJ月赛-2008年4月

解决方案1

利用map但是超时了

#include <iostream> #include <map> using namespace std; int main() { int n, m, max = 0; map <int, int> number; map <int, int>::iterator iter; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { scanf("%d", &m); iter = number.find(m); if (iter == number.end()) { number.insert(map <int, int>::value_type(m, 1)); } else iter->second++; } for (iter = number.begin(); iter != number.end(); iter++) { if (iter->second > max) { max = iter->second; m = iter->first; } } printf("%d\n", m); number.clear(); max = 0; } return 0; }

解决方案2

直接sort()

#include <iostream> #include <algorithm> using namespace std; int a[100000]; int main(){ int i,t,tcnt,ans,val; while(scanf("%d",&t)!=EOF) { for(i=0;i<t;i++) { scanf("%d",&a[i]); } sort(a, a + t); ans=1;tcnt=1; val=a[0]; //找出众数 for(i=0;i<t-1;i++) { if(a[i]==a[i+1]) tcnt++; else { if(tcnt>ans){ans=tcnt;val=a[i-1];} tcnt=1; } } if(tcnt>ans){ans=tcnt;val=a[t-1];} printf("%d\n",val); } return 0; }

解决方案3

原文：https://blog.csdn.net/tao_tao_bu_jue/article/details/3147794

利用堆来排序，再遍历找出最小众数

#include <iostream> #include <algorithm> using namespace std; int heap[100000], hsize = 0, a[100000]; inline void insert(int n){ int p,c=hsize; heap[hsize++]=n; //p为c的父节点 p=(c-1)/2; //最后c为1或2 while(c) { //小顶堆 if(heap[p]>heap[c]) { //通过三次异或，数值交换 heap[p]^=heap[c]; heap[c]^=heap[p]; heap[p]^=heap[c]; //沿着父节点不断往上判断交换 c=p; p=(c-1)/2; } else return; } } inline void update(int p){ int mt,l,r; //找出p的最小子节点 l=2*p+1; r=2*p+2; if(l>=hsize&&r>=hsize)return; if(r>=hsize) mt=l; else mt=heap[l]<heap[r]?l:r; if(heap[p]>heap[mt]){ //交换 heap[p]^=heap[mt]; heap[mt]^=heap[p]; heap[p]^=heap[mt]; //向下不断交换 update(mt); } } inline int del(){ //取出堆顶的值（最小值） int ret=heap[0]; hsize--; //把堆尾的值放到堆顶 heap[0]^=heap[hsize]; heap[hsize]^=heap[0]; heap[0]^=heap[hsize]; //更新堆 update(0); return ret; } int main(){ int i,t,n,tcnt,ans,val; while(scanf("%d",&t)!=EOF) { //将输入的数据插入堆 for(i=hsize=0;i<t;i++) { scanf("%d",&n); insert(n); } ans=1;tcnt=1; //出堆放入a[] for(i=0;i<t;i++) a[i]=del(); val=a[0]; //找出众数 for(i=0;i<t-1;i++) { if(a[i]==a[i+1]) tcnt++; else { if(tcnt>ans){ans=tcnt;val=a[i-1];} tcnt=1; } } if(tcnt>ans){ans=tcnt;val=a[t-1];} printf("%d\n",val); } return 0; }