雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::


    题目:数组中有三个数只出现一次,其它的数恰好出现两次,找出这三个数。

 

    先考虑“只有两个数出现一次”的情况:可以找到一种方法,将数组划分为两部分,且让这两个数分别在不同部分,这样每部分所有数的异或值,恰好分别等于这两个数。一种简单的分法就是,先计算出这两个数的异或值M(等价于求数组中所有数的异或值),求出M值的二进制表示中的最低位1(其它位的1也可以,只不过麻烦点)在 +k位,然后根据 +k位是否为1,将原数组分为两部分。

   

    回到原题,假设这三个不同的数是:ABC,它们的异或值 X = A xor B xor CX值可能为0,也可能不为0。当X值不为0时(比如:这三个数为357X值为1),很难找到一种方法,将原来的数组划分为两部分,使得这三个数不都在同一部分。因而,要先对原来的数组进行一次替换:将每个数与X进行异或。这样原来的三个数就变成了:

B xor CA xor CA xor B。记a = B xor Cb = A xor Cc = A xor B。新的异或值 x = a xor b xor c = 0

   

    由于ABC互不相等,显然它们间的异或值abc都不为0,且互不相等。(若a等于b,则 0 = a xor b = (B xor C) xor (A xor C) = A xor B != 0自相矛盾)

  

若三个数的异或值为0,且其中一个数在 +n位(n为任意值)上为1,则另两个数在 +n位上必然一个为1,另一个为0(不然的话,这三个数的异或值就不会为0),因而根据 +n位为1,可以将这三个数分成两部分

 

f(x)x的二进制表示中最低位1的位置,则f(a)f(b)f(c)这三个数中有且只有两个数相等。证明:不妨设f(a)f(b)f(c)中最小的是f(a)k = f(a),则bc +k位上必然是一个为1,一个为0,不妨设b +k位为1,则根据f(x)的定义以及f(a)最小,可得f(b)等于f(a)f(c)大于f(a)。因而,新数组的数x对应的所有f(x)的总异或值等于f(c)

 

假设f(a)等于f(b)m = f(c),由于c +m位上为1,不妨设 b +m位也为1,则a +m位为0。根据 +m位是否为1,可将新数组分为两部分,每部分的异或值恰好都是 a = B xor C,可以求出数A(等于a xor X)。 将数A放入原来的数组,问题转为“只有两个数出现一次”的情况,利用前面提到的方法算出另两个数。总共需遍历数组4次。

 

 

代码:

 

#include <cstdio>

#include <cassert>

 

static inline int extract_rightmost_one(unsigned value) { return value & -value; }

 

// if a != b, m = extract_rightmost_one(a), n = extract_rightmost_one(b),

//             k = extract_rightmost_one(a ^ b)

// then m == n != k   or   m == k != n   or n == k != m

 

void print_three_unique_number(const int arr[], unsigned len)

{

 assert (len >= 3 && len % 2);

 const int* const beg = arr;

 const int* const end = arr + len;

 

 int xor3 = 0;

 for (const int* p = beg; p != end; ++p) xor3 ^= *p;

 

 int flag1 = 0;

 for (const int* p = beg; p != end; ++p) flag1 ^= extract_rightmost_one(*p ^ xor3);

 

 assert(flag1 != 0 && (flag1 & (flag1 - 1u)) == 0u); // flag1 == 2^^k

 

 int xor2 = 0;

 for (const int* p = beg; p != end; ++p) {

    const int value = *p ^ xor3;

    if (value & flag1) xor2 ^= value; //or:

    // if ((value & flag1) == 0) xor2 ^= value;

 }

 

 const int number1 = xor2 ^ xor3;

 const int flag2 = extract_rightmost_one(xor2);

 int number2 = (number1 & flag2) ? number1 : 0; // put number1 into the array

 for (const int* p = beg; p != end; ++p) {

    if (*p & flag2) number2 ^= *p;

 }

 

 const int number3 = xor2 ^ number2;

 printf("%d %d %d\n", number1, number2, number3);

}

 

上面的代码并不严格符合C++标准,而是假定机器采用补码表示负数(不采用补码表示的老古董,一般人也碰不到)。 另外要特别注意的是,一些计算最好先转为无符号数,避免溢出,最后再转回有符号数。因为标准假定有符号数间的计算不发生溢出,当实际上发生溢出时,就是UB行为,编译器若进行些激进的优化就得不到正确结果。

 

posted on 2013-03-21 22:00 flyinghearts 阅读(6909) 评论(4)  编辑 收藏 引用 所属分类: 算法

评论

# re: 面试题: 找出数组中三个只出现一次的数 2013-03-28 09:46 岁月漫步
先收藏,不过不喜欢这种异或,补码运算  回复  更多评论
  

# re: 面试题: 找出数组中三个只出现一次的数 2013-06-23 23:42 void
数组中恰好有 n 个数只出现奇数次,找出这 n 个数:先排序, 然后比较前二个数, 作稍微的讨论即可一直砍下去... 最后剩下这些数. O(nlogn).  回复  更多评论
  

# re: 面试题: 找出数组中三个只出现一次的数 2013-10-02 21:37 rrison
面试的时候肯定要你优化到O(n)的,O(nlogn)的算法虽然普适但是不符合要求。@void
  回复  更多评论
  

# re: 面试题: 找出数组中三个只出现一次的数 2014-10-16 14:51 3d
,当实际上发生溢出时,就是UB行为,编译器若进行些激进的优化就得不到正确结果。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理