u*****o
发帖数: 1224 | 1 就是一个ARRAY，所有的元素都出现了三次，只有一个出现了一次。找出这个一次的元
素。
SPACE(O(1)), TIME (O(N))的解法是这个用bit operator的。答案是在CAREERCUP里找
到的。。
int ones = 0;
int twos = 0;
int not_threes, x;
for (int i=0; i
x = A[i];
twos |= ones & x; ************
ones ^= x;
not_threes = ~(ones & twos);
ones &= not_threes;
twos &= not_threes;
}
这个题的原理是这样的，有两个集合分别盛出现过1次（ONES)和2次(TWOS)的元素（前
两行）如果
有出现了第三次的，就从ONES, TWOS把它踢出来（后三行）
我的问题就是那行被MARK星星的原理是什么，如果一个元素第二次出现，怎么就能把它
放进去了。。。
比如我ARRAY前4个是1，2，3，1的话
前三个loop走完，two里还应该是空的，ones里应该是0^1^2^3=0
好这时进去第四个元素，twos = twos |(0&1）=0啊，并没有把1放进去啊。。
我哪里走错了。。苦恼啊，大神们请指导！！ |
r**h
发帖数: 1288 | |
c********p
发帖数: 1969 | |
u*****o
发帖数: 1224 | 4 大牛哥! 你先别走！
例子我看懂了，原理也明白了，可我还是不明白我的例子为什么不WORK
1，2，3，1
走到第二个1的时候，明明ONES里的1和新来的1有COMMON BITS，应该被放进TWOS里的
但这时ONES结果是0了啊！1^2^3所有的BITS都被CANCEL掉了。太可恶了有没有！
【在 r**h 的大作中提到】
: http://www.geeksforgeeks.org/find-the-element-that-appears-once
: 话说我觉得这题太坑了啊
|
u*****o
发帖数: 1224 | 5 哦我突然想啊是不是bit operation和我想的不一样啊，ONES里其实一直存着1，2，3呢
，而不是存着结果0？可是ONES是一个INTEGER啊。。怎么能记住以前所有的ENTRY呢？ |
p*i
发帖数: 411 | 6 bits, not elements
【在 u*****o 的大作中提到】
: 就是一个ARRAY，所有的元素都出现了三次，只有一个出现了一次。找出这个一次的元
: 素。
: SPACE(O(1)), TIME (O(N))的解法是这个用bit operator的。答案是在CAREERCUP里找
: 到的。。
: int ones = 0;
: int twos = 0;
: int not_threes, x;
: for (int i=0; i: x = A[i];
: twos |= ones & x; ************
|
v********n
发帖数: 18 | 7 mark nn【在 ultrabo (似是故人来)的大作中提到：】n：就是一个ARRAY，所有的元素
都出现了三次，只有一个出现了一次。找出这个一次的元n：素。n：SPACE(O(1)),
TIME (O(N))的解法是这个用bit operator的。答案是在CAREERCUP里找n：到的。。n：
n： int ones = 0; n： int twos = 0; n……nn--n[发自未名空间Android客户
端] |
r*********n
发帖数: 4553 | |
r******l
发帖数: 10760 | 9 前三个loop之后twos不是空的啊，你不会自己算算看？
这个题的意思是，所有位(bit)都出现过3x次1，只有某几位出现过3x+1次1。找出那几
位就可以了。 |
J****3
发帖数: 427 | |
u*****o
发帖数: 1224 | |
w**s
发帖数: 339 | |
l***i
发帖数: 1309 | 13 It might be easier if you think about each number as if they are 1 bit each. |
p*****2
发帖数: 21240 | |
