• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-09-19)  算法/数据结构 评论关闭  27 
    文章评分 0 次,平均分 0.0

    今天看到一个题目“有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数”前提还不能用位图。想起以前做ACM那段时间,有做过类似的题目,使用异或来找出成双的整数序列中为单的那个数。

    来看下面3个题目:
    1. n个数,1, 2, 3, ..., n,除了其中的一个数以外,其它所有数都出现了2次,要求找出那个数。
    将所有的数进行异或,两个相同的数异或结果为0,故最终的结果就是只出现一次的那个数。

    2. n个数中,除了2个数以外,其它所有数都出现了2次,找出那两个数。
    假设这两个数为A,B,依然用前面异或的思路,最终异或的结果将是A^B的结果。虽然现在不能还不能确定这两个数,但是考虑到异或结果不为0,其结果的二进制表示中,肯定有为1的bit,找出该bit。
    这两个数的该bit必定一个为0,一个为1.根据该bit的值是否为1,将原来所有数分为两组,其中一组该bit为0,另外一组该bit为1. 这里再分别对这两组进行异或,得到的两个值就是最终要找的那两个数。

    3. 有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数
    与上面提到的第2个问题类似,只不过这里所有值都只出现了一次,并且缺失了2个。这里我们把1,2,...,10w这10w个数补充到原数组中,就与问题2一样了,用问题2的解法即可解决该问题。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/2111.html

    关于
    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享