荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
You are given an array that contains integers. The integers content is such that
every integer occurs 3 times in that array leaving one integer that appears only once
Fastest way to find that single integer
-- not using any external memory (except a few trivial variables).
eg: [2,1,4,5,1,4,2,2,4,1]
wwwyhx 发表于 2011-7-15 16:04 ![]()
假设所有的数都有相同重复的3个,那么如果以int a[32]来记录所有数对应位的1的总合,那么数组a里每个元素都可以被3整除。
如果想讨巧,可以用一个int数来标记,可以被3整除的位就是1,反之是0, 那么最后遍历完数组后这个int数就是要求的数
- int GetSole(int a[], int n)
- {
- assert(a && n > 0 && n%3 == 1);
- int one = 0;
- int two = 0;
- int three = 0;
- int mask = 0;
- for (int i = 0; i < n; i++)
- {
- int nTmp1 = one;
- int nTmp2 = two;
- int nTmp3 = three;
- one &= ~a[i];
- one |= a[i] & (~mask);
- one |= (nTmp3 & a[i]);
- two &= ~a[i];
- two |= (nTmp1 & a[i]);
- three &= ~a[i];
- three |= (nTmp2 & a[i]);
-
- mask |= a[i];
- }
- return one;
- }
复制代码 |
|