首页 > 代码库 > OJ2236“孤单数”题目报告

OJ2236“孤单数”题目报告

题目描述:有2n+1个数,其中有n对数字是成双出现的,有且仅有1个数字只有它自己一个。请你找出这个孤单数。

输入描述:

第一行有且只有一个正整数n(n<=500000)

第二行有2n+1个数ai(-10^9<=ai<=10^9)

输出描述:

有且只有一个数,输出这个孤单数。

 分析:
  乍一看这个题目,其实就类似于我们小时候玩过的一个纸牌游戏:抽乌龟。也就是说,有奇数张牌,只有一种牌有且只有一张,我们需要找的也就是这张“孤单牌”。那么很明显,不是“孤单数”的数字,必然有另一个和它相等的数字存在,因此,我就想到了一种方法,排序。没错,就是排序,我们只需要把这奇数张牌从小到大排序或者从大到小排序即可,当然,为方便起见,我们就从小到大排序,那么不是孤单数的数字的前面或者后面一个必定和它相等,因为有奇数个数字,那么必然存在最后一张才是孤单数的情况,因此,我想到了分类寻找,也就是先在前2n个数字中寻找孤单数,找不到时,最后一个数字必然是孤单数。接下来,代码就很容易实现了。
代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
int a[500001];
using namespace std;
int main(void)
{
int i,m,num,last,n,flag = 0;
scanf ("%d",&n);
for (i = 0; i < 2 * n + 1; i++)
{
scanf ("%d",&a[i]);
}
sort(a, a + 2 * n + 1);
num = 0;
m = a[0];
for (i = 0; i < 2 * n;i++)//先在前2n个数字中寻找孤单数
{
if(a[i] == m)
{
num++;//每个不是孤单数的数字必定有两个
if(num == 2)//当同一种数字有两个时,证明该数字不是要寻找的数字,于是从下一种数字开始寻找
{
num = 0;//下一种数字数量清零
m = a[i + 1];//将中间变量的值定义为下一种数字
}
}
else//当一种数字第一次出现的数字的后一个数字与其不相等时,证明该数字是孤单数
{
flag = 1;//将标记赋值为1
last = a[i - 1];//孤单数为上一个数字
break;//退出循环
}
}
if(!flag)//当标记为0,也就是没有在前2n个数字中找到孤单数时,证明最后一个数字为孤单数
{
last = a[i];
}
printf ("%d\n",last);//输出孤单数

return 0;

}

小结:从这到题目可以看到排序的巧妙使用,这道类似于寻找单身狗的题目可以利用排序,找到单身狗,同时,标记也发挥了很大的作用~~

 

OJ2236“孤单数”题目报告