首页 > HDOJ解题报告 > HDU 2095 Find your present

HDU 2095 Find your present

HDU 2095 Find your present, 题目地址http://acm.hdu.edu.cn/showproblem.php?pid=2095。水题范围。

题目大意:给定至多1000000个数,里面有一个数出现了奇数次(看题目也许是1次,不过不影响做题),其余的数全部出现偶数次,所有数的数值范围在2^31内,现在要求你找出那个出现奇数次的数。

解题思路:开始想用数组,但是发现开不了那么大,即便开出来也很有可能是Memory Limited Exceeded。后来想到用map,AC了。再想想应该还有其他方法,于是网上搜了下,用抑或运算可以解决。

关键就是0^A=A, A^B^B=A, A^(偶数个B)=A。现在解题代码就可以很简短了。

//Map版本
//Coded by 代码疯子
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

int main()
{
    int n, i, t;
    while(EOF != scanf("%d", &n), n)
    {
        map<int, int> v;
        for(i = 0; i < n; ++i)
        {
            scanf("%d", &t);
            ++v[t];
        }
        map<int, int>::iterator iter;
        for(iter = v.begin(); iter != v.end(); ++iter)
        {
            if(iter->second == 1)
            {
                printf("%d\n", iter->first);
                break;
            }
        }
    }
    return 0;
}
//抑或运算版本
//Coded by 代码疯子
#include <stdio.h>
int main()
{
    int res, n, i, tmp;
    while(1)
    {
        scanf("%d", &n);
        if(!n)break;
        for(i = res = 0; i < n; ++i)
        {
            scanf("%d", &tmp);
            res ^= tmp;
        }
        printf("%d\n", res);
    }
    return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> HDU 2095 Find your present
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: HDOJ解题报告 标签: , , , ,
  1. 2010年11月18日13:05 | #1

    其实,我是一个演员!
    我假装看懂后,点点头大声招呼!

    [回复]

  2. 2010年11月18日21:24 | #2

    呵,算法我是很少研究,学习了!

    [回复]

  3. 2010年11月20日22:24 | #3

    学习学习.

    [回复]

  4. 2010年11月21日09:11 | #4

    看不懂,支持下吧

    [回复]

  5. 2010年11月23日12:14 | #5

    @winson
    呵呵 各有各的研究

    [回复]

  6. 2010年11月23日12:15 | #6

    @Tiger
    很多人都这样 …… 有点讨厌哦

    [回复]

  7. 2010年11月23日12:16 | #7
  8. 浅蓝
    2014年12月8日22:11 | #8

    那个…我是最近几个月才开始刷题的纯小白,我用我的代码跟你的代码对比了一下,只有命名的差别,但是还是各种爆内存…

    [回复]

    代码疯子 回复:

    @浅蓝, 第一种方法可能是题目的评判标准变严格了吧,第二种方法肯定不会爆内存啊

    [回复]

    浅蓝 回复:

    @代码疯子, 谢谢,两种方法都已经过了,好像是那几天OJ出问题了,什么都是爆内存

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.