编程:找出数组中的特殊数

Categories: Program
Tags: No Tags
Comments: 1 Comment
Published on: 2012/11/28

若干年前在电子bbs【自由空间】上的一个题目,来源链接:http://thuee.net/bbscon.php?bid=13&id=64451

假设有一个数组P有3N+1个整数,其中有N个数每个出现3次,还有一个特殊数仅出现过一次,比如{a,a,a,b,b,b,c}。要求只遍历一遍数组将这个数找出来,空间复杂度O(1)。

如果是每个数只出现两次,那么只需要把所有的数异或起来就可以得到最终的结果了。那出现三次呢?下面这个程序巧妙地实现了这一点:

int A = 0, B = 0;
for (int I = 0; I < 3 * N + 1; I++)
{
    A ^= P[I] & ~B;
    B ^= P[I] & ~A;
}

这个程序是什么原理呢?

.

.

.

.

.

.

.

.

.
线
.

因为是按位运算,那么不同位之间的运算是相互独立的,所以我们可以假设所有的数都只有1比特。循环体每进行一次循环,如果P[I]的值为0,那么A和B的值不会发生变化。如果P[I]的值为1,那么(A,B)的值按照下面的顺序进行状态转移:

那么如果某一位若经过3K+1次转移,A为1;若经过3K次转移,A为0,故最终的A为所求数。

1 Comment - Leave a comment

Leave a comment

Your email address will not be published. Required fields are marked *


Close Print