d******v
发帖数: 801 | 1 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
int，用bit op做。 |
s********k
发帖数: 6180 | 2 先把所有不重复的sum，然后XOR（int），两者相减？
【在 d******v 的大作中提到】
: 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
: int，用bit op做。
|
d******b
发帖数: 73 | 3 这种代码也敢贴上来，证明就是 面试的时候 题意都没有弄清楚就瞎写。还有，就算离
题万里，那个 odd 连续 异或同一个数两次。鄙人不才，根本看不懂啊。 |
n*******7
发帖数: 181 | 4 x先排序，然后one pass看每组相同的数的开始位置就行了。
：一个int[ ]里面只有一个数字出现偶数次，其它的都出现奇数次，求这个出现偶数次
的数字。 |
b********0
发帖数: 62 | 5 3l的代码好像有问题 但是方向是对的
这个应该是用bit op的技巧达到O(n)时间
【在 n*******7 的大作中提到】
: x先排序，然后one pass看每组相同的数的开始位置就行了。
:
: ：一个int[ ]里面只有一个数字出现偶数次，其它的都出现奇数次，求这个出现偶数次
: 的数字。
|
y*****e
发帖数: 712 | 6 排序就nlogn了啊。
【在 n*******7 的大作中提到】
: x先排序，然后one pass看每组相同的数的开始位置就行了。
:
: ：一个int[ ]里面只有一个数字出现偶数次，其它的都出现奇数次，求这个出现偶数次
: 的数字。
|
h****t
发帖数: 69 | 7 抱歉之前是午饭前匆匆写下的， 的确有bug
O(n) time and O(n) space complexity 的算法用HashMap记录每个数字的次数，再过
一遍HashMap找出偶数次的数字就行了
我之前考虑的是O(n) time and O(1) space complexity 的算法， 用bit
manipulation and truth table. |
y*****e
发帖数: 712 | 8 lz可以改一下前面o1的答案吗？想学学这题用bit operation怎么做，赶脚gg不会接受
hashmap的答案的。。
【在 h****t 的大作中提到】
: 抱歉之前是午饭前匆匆写下的， 的确有bug
: O(n) time and O(n) space complexity 的算法用HashMap记录每个数字的次数，再过
: 一遍HashMap找出偶数次的数字就行了
: 我之前考虑的是O(n) time and O(1) space complexity 的算法， 用bit
: manipulation and truth table.
|
d******v
发帖数: 801 | 9 把题改了，加了要求用bit op做。这题是single number的变体，不搞出个bit op做法
，interviewer不会放过关的。 |
f******w
发帖数: 2 | 10 (XOR all) XOR ( OR all)
【在 d******v 的大作中提到】
: 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
: int，用bit op做。
|
|
|
l*****8
发帖数: 1083 | 11 这个不对吧
这题怎么bit op。。。
【在 f******w 的大作中提到】
: (XOR all) XOR ( OR all)
|
f******w
发帖数: 2 | 12 U do XOR and OR for bits.
【在 l*****8 的大作中提到】
: 这个不对吧
: 这题怎么bit op。。。
|
l*****8
发帖数: 1083 | 13 我知道bit operation，你给的solution好像不对，一个反例：1, 3, 3返回2， 原数的
信息丢失了。
【在 f******w 的大作中提到】
: U do XOR and OR for bits.
|
d******v
发帖数: 801 | 14 好像不对，假设数组｛A, B, C, D, E, E} = {00, 01, 10, 11, E, E}。
1）xor all = 00 ^ E ^ E = 00 当E为任何值都成立
2）or all = 11 | E | E = 11 当E为任何值都成立
3）所以(xor all) xor (or all) = 11 当E为任何值都成立
【在 f******w 的大作中提到】
: (XOR all) XOR ( OR all)
|
m*****k
发帖数: 18 | 15 1. 扫一遍数组，XOR所有Unique number一次，得一数x
2. XOR 原数组所有数，再XOR x，返回此结果便是
O(n) time, O(n) space |
l*****8
发帖数: 1083 | 16 这个可行，但要找所有unique number还是要用hashset，这样用bit op就没什么优势。
【在 m*****k 的大作中提到】
: 1. 扫一遍数组，XOR所有Unique number一次，得一数x
: 2. XOR 原数组所有数，再XOR x，返回此结果便是
: O(n) time, O(n) space
|
s********k
发帖数: 6180 | 17 用OR加bit map算出来数组里面出现哪些数字，然后用XOR去处奇数的
【在 d******v 的大作中提到】
: 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
: int，用bit op做。
|
p****y
发帖数: 67 | 18 可以用两个bit来记一个数的次数 一开始00. 出现一次后变01再出现变10
每次出现的话。00->01. 01->10. 10->01. 最后把和10对应的数就好了 |
d******v
发帖数: 801 | 19 这个和用HashMap记录有什么区别吗？都是O(n)space
【在 p****y 的大作中提到】
: 可以用两个bit来记一个数的次数 一开始00. 出现一次后变01再出现变10
: 每次出现的话。00->01. 01->10. 10->01. 最后把和10对应的数就好了
|
p**t
发帖数: 157 | 20 类似single number II吧？
maintain 2个变量 odd even
初始状态每个bit都是出现了偶数次 所以even设全1
然后对每个数按位xor
假如某一位在even里为1 且当前数对应位为1
或者在odd里为1 且当前数对应位为0
则将odd的对应位设1 odd位设0
反之类似
temp = odd;
odd = even ^ int[i] | odd ^ ~(int[i]);
even = temp ^ int[i] | even ^ ~(int[i]);
最后所有数处理过一遍之后 所求的数就存在odd里
【在 d******v 的大作中提到】
: 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
: int，用bit op做。
|
|
|
h****t
发帖数: 69 | 21 我3L就是这个想法，但是有3个问题
1）无法分辨出现0次和偶数次的数字
2）num={2,3,4,4}, output = 6 = 110, 因为2，3导致2^1 bit 位出现偶数次
3）num = {3,3,1}, output = 2, 因为1导致2^0 bit 位出现奇数次
【在 p**t 的大作中提到】
: 类似single number II吧？
: maintain 2个变量 odd even
: 初始状态每个bit都是出现了偶数次 所以even设全1
: 然后对每个数按位xor
: 假如某一位在even里为1 且当前数对应位为1
: 或者在odd里为1 且当前数对应位为0
: 则将odd的对应位设1 odd位设0
: 反之类似
: temp = odd;
: odd = even ^ int[i] | odd ^ ~(int[i]);
|
c*****m
发帖数: 271 | 22 or加bit map算出来数组里面出现哪些数字，怎么搞？
【在 s********k 的大作中提到】
: 用OR加bit map算出来数组里面出现哪些数字，然后用XOR去处奇数的
|
p**t
发帖数: 157 | 23 1. 不需要知道出现0次
某个bit如果从始至终出现0次 那么你想找的那个数对应bit也必然是0
2. 人家说了只有1个数字出现奇数次 你2 3 都出现奇数次当然不work
3. output怎么可能是2 要找的就是第一位出现奇数次的那些位好么
3 = 011
init: odd = 000 even = 111
i = 1:
odd = 011 eve = 100
i = 2:
odd = 000 eve = 111
i = 3:
odd = 001 eve = 110
done
【在 h****t 的大作中提到】
: 我3L就是这个想法，但是有3个问题
: 1）无法分辨出现0次和偶数次的数字
: 2）num={2,3,4,4}, output = 6 = 110, 因为2，3导致2^1 bit 位出现偶数次
: 3）num = {3,3,1}, output = 2, 因为1导致2^0 bit 位出现奇数次
|
h****t
发帖数: 69 | 24 1) 看3
2）"只有1个数字出现奇数次" --- 拜托仔细看题
3）even 初始应该是
1111 1111 1111 1111 1111 1111 1111 1111
而不是
0000 0000 0000 0000 0000 0000 0000 0111
而且你最后
odd = 1, even = 6
如何推导出3？ |
s********i
发帖数: 74 | 25
题目是只有一个出现偶数次。
【在 p**t 的大作中提到】
: 1. 不需要知道出现0次
: 某个bit如果从始至终出现0次 那么你想找的那个数对应bit也必然是0
: 2. 人家说了只有1个数字出现奇数次 你2 3 都出现奇数次当然不work
: 3. output怎么可能是2 要找的就是第一位出现奇数次的那些位好么
: 3 = 011
: init: odd = 000 even = 111
: i = 1:
: odd = 011 eve = 100
: i = 2:
: odd = 000 eve = 111
|
f*********s
发帖数: 34 | 26 Use last bit to separate numbers into two groups, then use the next last bit
to further separate them, remove any single number, keep doing it, the last
pair is the even number.
Complexity is still n*lgn though. |
I*******g
发帖数: 7600 | 27 你这是脱裤子放屁吗？
bit
last
【在 f*********s 的大作中提到】
: Use last bit to separate numbers into two groups, then use the next last bit
: to further separate them, remove any single number, keep doing it, the last
: pair is the even number.
: Complexity is still n*lgn though.
|
f*********s
发帖数: 34 | 28 000, 001, 010, 011, 111, 100, 100
step 1: (use last bit)
000, 010, 100, 100
001, 011, 111
step 2: (use second last bit)
000, 100, 100
010 - remove
001 - remove
011, 111
step 3: (use first bit)
000 (remove)
100, 100
011 (remove)
111 (remove)
final: 100, 100 are remaining |
f*********s
发帖数: 34 | 29
Please elaborate.
Thanks.
【在 I*******g 的大作中提到】
: 你这是脱裤子放屁吗？
:
: bit
: last
|
p**t
发帖数: 157 | 30 3其实我只是假设了每个数字只有3位而已 32位还是3位没有任何区别
当然我确实看错题了。。。我以为是只有1个出现奇数次。。。
1) 看3
2）"只有1个数字出现奇数次" --- 拜托仔细看题
3）even 初始应该是
1111 1111 1111 1111 1111 1111 1111 1111
而不是
0000 0000 0000 0000 0000 0000 0000 0111
而且你最后
odd = 1, even = 6
如何推导出3？
【在 h****t 的大作中提到】
: 1) 看3
: 2）"只有1个数字出现奇数次" --- 拜托仔细看题
: 3）even 初始应该是
: 1111 1111 1111 1111 1111 1111 1111 1111
: 而不是
: 0000 0000 0000 0000 0000 0000 0000 0111
: 而且你最后
: odd = 1, even = 6
: 如何推导出3？
|
|
|
f*********s
发帖数: 34 | 31
Correction:
1. Complexity is n*lg(max(n)), so this algorithm works well if there are
large amount of repetitive smaller numbers;
2. In the last step, there should exist only one group with even number of
elements which has the even number;
【在 f*********s 的大作中提到】
: 000, 001, 010, 011, 111, 100, 100
: step 1: (use last bit)
: 000, 010, 100, 100
: 001, 011, 111
: step 2: (use second last bit)
: 000, 100, 100
: 010 - remove
: 001 - remove
: 011, 111
: step 3: (use first bit)
|
h****t
发帖数: 69 | 32 4k的方法我也想过了， 但是因为问题2一样行不通
比较极端的反例是
{8, 8, 6, 5, 3} = {0b1000, 0b1000, 0b0110, 0b0101, 0b0011}
每一个bit位1出现的次数都是偶数 |
p**t
发帖数: 157 | 33 发完我就想到问题所以d了。。。
我在想。。。
【在 h****t 的大作中提到】
: 4k的方法我也想过了， 但是因为问题2一样行不通
: 比较极端的反例是
: {8, 8, 6, 5, 3} = {0b1000, 0b1000, 0b0110, 0b0101, 0b0011}
: 每一个bit位1出现的次数都是偶数
|
y*****9
发帖数: 149 | 34 这样行不？
int twos = 0;
int ones = 0;
for (int i = 0; i < A.size(); i++){
x = A[i];
twos = ones & x;
ones = ones ^ x;
}
return twos |
p**t
发帖数: 157 | 35 你这逻辑是什么。。。
【在 y*****9 的大作中提到】
: 这样行不？
: int twos = 0;
: int ones = 0;
: for (int i = 0; i < A.size(); i++){
: x = A[i];
: twos = ones & x;
: ones = ones ^ x;
: }
: return twos
|
I*******g
发帖数: 7600 | 36 很简单：
只要两个变量
Space：O(1)
Time: O(n)
BigInteger bit = new BigInteger("0");
int temp1 =0;
for(int x:array){
if (!bit.testBit(x)){
bit =bit.setBit(x);
temp1 ^= x;
}
}
for(int x:array){
temp1 ^= x;
}
System.out.println(temp1); |
p**t
发帖数: 157 | 37 你确定你不是和我一样看错题了？
【在 I*******g 的大作中提到】
: 很简单：
: 只要两个变量
: Space：O(1)
: Time: O(n)
: BigInteger bit = new BigInteger("0");
: int temp1 =0;
: for(int x:array){
: if (!bit.testBit(x)){
: bit =bit.setBit(x);
: temp1 ^= x;
|
I*******g
发帖数: 7600 | 38 你随便拿我的程序去测试：
e.g
int [] array = {1,1,1,2,2,3,3,3,5};
return: 2
【在 p**t 的大作中提到】
: 你确定你不是和我一样看错题了？
|
I*******g
发帖数: 7600 | 39 你没有看懂， 就不要乱说。
【在 p**t 的大作中提到】
: 你确定你不是和我一样看错题了？
|
p**t
发帖数: 157 | 40 我放狗搜了一下
其实班上曾经出现过这个题
当时也没有更好的办法
用bit op也可以 但是同样是脱了裤子放屁的算法
首先你得知道数组里都有哪些数字 或者说 先去重
然后把所有出现过的数字XOR 再依次和数组XOR
这相当于是把数组里每个数的频率都+1再转化成简单问题
但是。。。无序数组去重本身想O(n)就得hash
或者分配一块2^32的内存空间做bit map
哪个都不如直接hash了。。。
【在 h****t 的大作中提到】
: 4k的方法我也想过了， 但是因为问题2一样行不通
: 比较极端的反例是
: {8, 8, 6, 5, 3} = {0b1000, 0b1000, 0b0110, 0b0101, 0b0011}
: 每一个bit位1出现的次数都是偶数
|
|
|
f*********s
发帖数: 34 | 41
Smart!!!
Basically the first loop XOR every number exactly once,
second loop XOR again to every number, which made odd number XOR twice, and
even number XOR odd times.
It turned one Even number problem into one Odd number problem.
【在 I*******g 的大作中提到】
: 很简单：
: 只要两个变量
: Space：O(1)
: Time: O(n)
: BigInteger bit = new BigInteger("0");
: int temp1 =0;
: for(int x:array){
: if (!bit.testBit(x)){
: bit =bit.setBit(x);
: temp1 ^= x;
|
p**t
发帖数: 157 | 42 好吧 你相当于是用了512MB的一块内存做去重了。。。
【在 I*******g 的大作中提到】
: 很简单：
: 只要两个变量
: Space：O(1)
: Time: O(n)
: BigInteger bit = new BigInteger("0");
: int temp1 =0;
: for(int x:array){
: if (!bit.testBit(x)){
: bit =bit.setBit(x);
: temp1 ^= x;
|
p**t
发帖数: 157 | 43 用biginteger做去重能处理负数的情况么。。。
是不是还得转成uint？
【在 I*******g 的大作中提到】
: 你没有看懂， 就不要乱说。
|
h****t
发帖数: 69 | 44 x< 0 的话?
当然你的方法理论上是 O(1) space, 但是worst case 需要 2^32 bit = 4 Gb.
【在 I*******g 的大作中提到】
: 很简单：
: 只要两个变量
: Space：O(1)
: Time: O(n)
: BigInteger bit = new BigInteger("0");
: int temp1 =0;
: for(int x:array){
: if (!bit.testBit(x)){
: bit =bit.setBit(x);
: temp1 ^= x;
|
p**t
发帖数: 157 | 45 转成unsign int呗。。。
这倒不是大问题
【在 h****t 的大作中提到】
: x< 0 的话?
: 当然你的方法理论上是 O(1) space, 但是worst case 需要 2^32 bit = 4 Gb.
|
r****7
发帖数: 2282 | 46 只有1个出现奇数次需要整那么麻烦么。。。
【在 p**t 的大作中提到】
: 3其实我只是假设了每个数字只有3位而已 32位还是3位没有任何区别
: 当然我确实看错题了。。。我以为是只有1个出现奇数次。。。
:
: 1) 看3
: 2）"只有1个数字出现奇数次" --- 拜托仔细看题
: 3）even 初始应该是
: 1111 1111 1111 1111 1111 1111 1111 1111
: 而不是
: 0000 0000 0000 0000 0000 0000 0000 0111
: 而且你最后
|
f*********s
发帖数: 34 | 47
First loop can use HashSet to save memory.
The idea is to turn one Even problem to one Odd problem.
Like 1,2,3,3
After first loop we get 1,2,3
Put 1,2,3 back we got 1,2,3,1,2,3,3, now we have three 3s.
【在 p**t 的大作中提到】
: 转成unsign int呗。。。
: 这倒不是大问题
|
h****t
发帖数: 69 | 48 的确，总的来说我也认为如果数字的范围没有限制的话应该没有真正意义上的O(n)time
and O(1) space解法
【在 p**t 的大作中提到】
: 转成unsign int呗。。。
: 这倒不是大问题
|
p**t
发帖数: 157 | 49 如果用hashset 直接unordered_map计数就好了 为什么还要用XOR。。。
【在 f*********s 的大作中提到】
:
: First loop can use HashSet to save memory.
: The idea is to turn one Even problem to one Odd problem.
: Like 1,2,3,3
: After first loop we get 1,2,3
: Put 1,2,3 back we got 1,2,3,1,2,3,3, now we have three 3s.
|
p**t
发帖数: 157 | 50 如果所有数字出现次数已知并且相同的话可以有
但是只告诉你出现奇数次 偶数次 那应该是不行的。。。
time
【在 h****t 的大作中提到】
: 的确，总的来说我也认为如果数字的范围没有限制的话应该没有真正意义上的O(n)time
: and O(1) space解法
|
|
|
y*****e
发帖数: 712 | 51 lz，题目真的没有其他条件吗？比如range是1到n之类的？狗狗家bar是高，但也没必要
出这样的题来为难面试者吧。。。 |
k******e
发帖数: 145 | |
d******v
发帖数: 801 | 53 这是看来的面经，具体我也不知道啊
【在 y*****e 的大作中提到】
: lz，题目真的没有其他条件吗？比如range是1到n之类的？狗狗家bar是高，但也没必要
: 出这样的题来为难面试者吧。。。
|
s*******z
发帖数: 14 | 54 楼主这个bitoperation 的要求是你想出来的还是面试官提出的？
【在 d******v 的大作中提到】
: 把题改了，加了要求用bit op做。这题是single number的变体，不搞出个bit op做法
: ，interviewer不会放过关的。
|
h**********c
发帖数: 4120 | 55 good question
mark in TODO list.
【在 d******v 的大作中提到】
: 一个int[ ]里面只有一个int出现偶数次，其它的都出现奇数次，求这个出现偶数次的
: int，用bit op做。
|
