现在的位置: 首页 > 综合 > 正文

找出数组中只出现过一次的数

2011年04月26日 ⁄ 综合 ⁄ 共 399字 ⁄ 字号 评论关闭

一个大数组,在1到25000之间,只有4K memory, 打印出其中正好只出现过一次的数。没出现过,出现过2次,3次,或更多,都不打印。

 

solutions:

  1)位图法,但每个数有3个状态:0,1,>1.因此需要2 bit,  (25000 * 2) /(8*1024) = 6.1k,内存占用符合要求。

  2)压缩,解法1中,用2个bit表示3种状态,事实上浪费了一个状态(2bit可以表示4种状态),因此可以考虑多个数共用几个bit表示状态,如:

     5个数共用4个bit来表示,则(25000/5) * 4 / ( 8*1024) = 2.44k,内存占用符合要求,但是代码相对写起来恶心些。

  3)时间换空间,还是每个整数用2个bit表示,但分多次打印,如分5次扫描:第1次只扫1~5000内的整数,第2次只扫5001~10000的。。。

    每次用内存:5000*2/(8*1024) = 1.22k,逻辑比较简单,就是慢些。

抱歉!评论已关闭.