Dec 13

找相同,找不同:继续,再继续。 不指定

felix021 @ 2009-12-13 17:58 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(8048) | Via 本站原创 | |
由于上次和slyar同学提起这个问题,所以才想着还是自己再写一下,而且其实还有自己没解决的问题,希望能抛砖引玉。

剧透
本篇未解决的问题是:在n个数字里面,如果只有3个数字是没有凑对的,能否用O(n)的方法找出来?超过3个又远小于n个的情况呢?

===

WOJ上有2道连在一起的题目,很赞。

找不同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203

找不同:给你n*2+1个数,其中有n对是一样的,让你找出没有相同数字的那一个(真寂寞)。
如果我们能把所有的数字按大小排序,那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况,就是找到寂寞数字了时候。
可是这样效率太低,就算用基数排序,那个常数也是够大的。
换个思路,由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说,按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0,且该操作是可交换的。
所以如果我们将所有数字串起来异或,其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0,最后异或的结果就是最寂寞的那个。。

找相同:有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明,如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab,如果a,b相同,放回去,如果a,b不同,都舍弃】直到剩下来的所有数字都相同(这一定是可以达到的)。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的,用栈。伪码如下
init stack(s)
for x in a[1..n]
    if empty(s) or s.top() == x
        s.push(x)
    else
        s.pop()
return s.top()


如果有同学看看1204的话,就会知道,这题是
继续找相同:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述:有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别,多了一种情况就是,有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了,但是只要稍微想想,其实还是很容易的:
用上面的方法处理前1~n-1个数字,到了最后一个数字的时候,看看和栈里面那个数字是不是一样
如果一样,说明这个数字出现了超过一半次,输出
如果不一样,那么栈里肯定只剩下一个数字,能出现一半次的,肯定是这两个数字之一,重新扫一次数组就行了。

WOJ关于找相同和不同的貌似就只有三道题,但是“继续”其实还没完。

继续找不同:有2n个数字,其中2n-2个数字是两两凑对的,剩下两个数字很寂寞,请找出来。
这题和前面的找不同也很像,解决方法是可以“复用”的。
以前的一篇日志里面有:http://www.felix021.com/blog/read.php?1243
解法是momodi给出的,将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B,不符合要求)
然后扫描C的每一bit,如果bit[k] == 1,那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A,然后A ^ C = B
这种解法也是O(n)的,只需要扫描两遍,还是比较快的。

-------------------------------------
最后,重点:
如果是3个数,或者更多一些,有没有O(n)的解法?
当然,用O(n)的基数排序处理以后再遍历,的确是O(n)的效率,但是就是效率太低了,而且需要多次遍历。
假设数字的量超过1000亿,需要存放在硬盘中(也就是扫描次数越少越好),这该怎么办呢?

心里已经有些想法了,不过暂时不想写出来,再想想明白。
如果哪位大牛有好的想法,希望互相交流一下:)



欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
lzonline01
2011-3-26 23:22
你给出来的那个算法不是最优的空间很大n/2,还可以优化到O(1)
jjymhkx0820 Email
2009-12-28 10:45
如果 三个数字的这一位都是0的话,异或之后的数字应该是 1 吧。PS,上面的方法要加入个奇偶计数哈。
felix021 回复于 2009-12-28 12:42
0 | 0 = 0
jjymhkx0820 Email
2009-12-22 12:53
先集体^,得出了d =  A^B^C, 按照位扫描 d,若d的bit[k]位为 0,说明 A B C 中,有一个在 bit[k] 位和另外两个不同。这样大概就分成了 1个不成对 + 2个不成对问题了。。
felix021 回复于 2009-12-22 12:57
显然这个证明是错误的,如果三个数字的这一位都是0呢?
slyar Email Homepage
2009-12-18 21:02
扫两遍那种是O(n)么...可以这么算的?
felix021 回复于 2009-12-19 00:15
当然算啊。。如果C是常数,那么O(cn)就是O(n)
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]