Vijos1917 艾酱最喜欢的数字 [求绝对众数]

1.题意：第一行一个数字N，表示一共有多少个数字，第二行N个数字，保证其中至少有一个数字出现次数超过一半，任务是求出这个出现最多的数。

2.分析：本题是明显的求众数的问题，常规思路为开一个大数组，在读入数据的同时统计数据出现的次数，最后遍历出众数，显然的提交之后会MLE，因为题面上的数据范围为：

40%的数据满足(n<=100)
60%的数据满足(n<=1000000)，内存大小限制128Mb
70%的数据满足(n<=1000000)，内存大小限制3Mb
100%的数据满足(n<=1000000)，且所使用内存大小不能超过1Mb

所有输入数字为小于1000000007的非负整数。

那么这里提供一个新的思路：即不用数组统计出现次数，因为最终关注的只是众数，无需记录所有信息。

考察绝对众数的两个性质：（1）众数的出现次数严格大于总数字的一半；（2）删除数组中两个不同的数，绝对众数不变

通过不断删除两个不同的数，最终剩下一个或者两个数的时候，留下的一定是单独的一个绝对众数（数组有奇数个数）或者两个绝对众数（数组有偶数个数）

具体操作是维护两个变量num以及temp分别表示临时众数与当前读入的数字，一个num_cnt表示已经遇到的临时众数的数量

当num != temp 则忽略这两个数：temp继续读入下一个数。num_cnt--

当num = temp 则忽略temp，增加num的个数：temp继续读入下一个数,num_cnt++

当num_cnt为0，选取下一个temp为num

代码如下：

 # include <iostream>

 # include <cstdio>

 using namespace std;

 int N;

 int main()

 {

     while(scanf("%d",&N)!=EOF)

     {

         int num;

         int num_cnt=;

         scanf("%d",&num);

         for(int i=;i<N;i++)

         {

             int temp;

             scanf("%d",&temp);

             if(num_cnt==)

             {

                 num=temp;

                 num_cnt=;

                 continue;

             }

             if(temp==num)

                 num_cnt++;

             else

                 num_cnt--;

         }

         printf("%d\n",num);

     }

     return ;

 }

巴特西

Vijos1917 艾酱最喜欢的数字 [求绝对众数]

最新文章

热门文章