在整数序列中查找缺失的项

2013年9月19日 由 Creater 留言 »

今天看到一个题目“有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的解法即可解决该问题。

广告位

评论已关闭.