趣题:寻找出现了奇数次的数

1. 给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数,其中有且仅有两个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

 
 

1. 从头到尾异或一遍,最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质:两次异或同一个数,结果不变。再考虑到异或运算满足交换律,先异或和后异或都是一样的,因此这个算法显然正确。

2. 从头到尾异或一遍,你就得到了需要求的两个数异或后的值。这两个数显然不相等,异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位,然后把所有这n个数分成两类,在那一位上是0的分成一类,在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

题目来源:http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1


    来自TopLanguage的朋友们,你们好!!
    经常看网站的来路分析是一件很有意义的事情。很多牛B东西都是我在回访来路时找到的。牛人Pongba从03年开始就在CSDN上写Blog,每一篇文章都是经典的原创牛文,访问量巨大无比。他在Google Groups里建了一个group叫做TopLanguage,里边真是牛人如云。如果你对程序设计一类的东西感兴趣,你会喜欢这个group的。
    向Pongda和TopLanguage的牛人们表示深深的膜拜。

24 条评论

  • Jolie

    请问个问题啊,在c中如何实现对c语句文件(任何形式,可以是.c也可以是.txt)扫描功能呀?
    目的是辨认出运算符,比如||,&&,+,-,*,/
    并进行替换。

    困惑好几个月的问题。。。我在网上也没有找到语句扫描的c,只有端口扫描的。。。。
    欢迎与我联系:msn:ayahmy@hotmail.com

  • pongba

    感谢Matrix67的介绍:-)

    顺便给一个这个问题的(一种可能的)启发式解题过程分析,免得朋友们查找:
    http://groups.google.com/group/pongba/browse_frm/thread/76b57a772b5ca091#
    有兴趣与解题思维分析的朋友可以讨论讨论:)

  • cosechy

    楼上上上:c是纯编译的语言所以应该没有直接的办法。办法是,调用c编译器每次都编译一下或者复制一下c或者类似语言的代码。当然要不是运行的时候干这事的话#include就可以了

  • 呵呵

    对不对呢?对就给个留言吧

    1.全部异或,得到的就是答案

    2.分治法,1*先保证数据随机化(随机打乱O(n))
    2*选定x,所有比x小的在左面,大的在右面O(n)
    3*左面的全部异或得p,右面的全部异或得q O(n)
    4*如果p0,q0,p,q就是答案,输出
    如果p=0那么在得到q的那半继续执行以上算法

    时间复杂度分析T(n)=T(n/2)+O(n),
    Mater Theory告诉我们这个T(n)=O(n)。
    不知道对不对?

  • 呵呵

    汗,楼上都说了算法了。。我晚了。。

  • 对酒当歌

    在所有m×n的扫雷格局中,求数字和最大的那一局?

  • Earthson

    如果我不能开辟一个数组存下这个数组(这个序列非常大),我能做的只是把这个序列扫描一遍。怎么找到序列中有且仅有的两个出现奇数次的数呢?

  • Earthson

    终于知道了 把ls的算法改进下:
    假设在某个二进制位这两个数是不同的(这个必然成立,否则两数相等)
    这个二进制位就能把数分成两组,这两个数分列两侧,左边异或的结果和右边异或的结果即分别为这两个数。于是得到一个O(n)的算法

  • glq2000

    http://hi.baidu.com/huyuanming11/blog/item/340daeb05e8ace580823021d.html 这里提到一个类似的题目:
    给出1..n的一个排列,其中缺少2个元素,用O(1)的空间找到那2个缺失的元素。 假设缺失的两个数为A和B,可以得到A+B以及A^B的值,但由这两个值求不出A B来。。 楼主有何思路么?

  • glq2000

    我后来想还可以构造 A^2 + B^2的值,但这样也可能会溢出,比如n是10000的话, 1^2+2^2+3^2+…+n^2=n(n+1)(2n+1)/6 ,此时n(n+1)(2n+1)/6的值已经溢出了。。

  • wenanguo

    如果恰有三个数出现奇数次呢

  • |Psycho_Mantis|

    ……这篇日志的日期……前几层楼都好淡定……

  • superb

    有人写过第二个算法的实现吗?我觉的这个算法是有问题的,
    比如说有四个数, 103, 103, 104, 134, 写成二进制是:
    01100111
    01100111
    01101000
    10000110

    xor后得到:
    11101110

    然后按异或后的结果,按位计算该位上是0和1时,两个数中相应位是0还是1的情况。

    但是问题是,怎么把每一位上的结果组合成这两个数呢?我们不知道这两个数在不同位上对应的01的情况,也就没有办法把这些结果组合起来吧。。。

    可能是我还没有理解这个算法,欢迎解惑。。有代码最好。。

  • MoMo

    @17楼: 我的理解是这个意思,这四个数103, 103, 104, 134的异或就是104和134的异或,结果肯定不为0,那么具体到二进制就至少有一位是1,比如你异或他们的二进制结果是11101110,那么右手边数起的第二位为1,那说明出现了104和134的二进制在第二位是不一样的,因此我们根据第二位把整个数组分两组,一组是第二位含1的,一组是第二位含0的,对每一组来说,又回到第一个问题了

  • Ernest

    如果是3个出现奇数次的数怎么办?如果是k个?

  • cervelo

    为什么,什么哲理都能用数字来分解、

  • TC

    留个名。。看这个博客好多天了,疯狂补习,希望能考进姚班哈哈😄

回复给 呵呵 取消回复

11  +    =  13