e*****e
发帖数: 1275 | 1 地球人都知道如果只有一个整数咋办。XOR~~~~~
如果是n个整数出现奇数次,怎么搞？ |
P*******b
发帖数: 1001 | 2 bitset不行吗？
【在 e*****e 的大作中提到】
: 地球人都知道如果只有一个整数咋办。XOR~~~~~
: 如果是n个整数出现奇数次,怎么搞？
|
e*****e
发帖数: 1275 | 3 能详细说说吗？
多谢！！
【在 P*******b 的大作中提到】
: bitset不行吗？
|
d**e
发帖数: 6098 | 4 我能不能问问这题具体是什么？
这些数有范围的吗？是连续的吗？
跟那题不见一个数的是不一样吧？
【在 e*****e 的大作中提到】
: 地球人都知道如果只有一个整数咋办。XOR~~~~~
: 如果是n个整数出现奇数次,怎么搞？
|
e*****e
发帖数: 1275 | 5 You are given an array containing positive integers. All the integers occur
even number of times except one. Find this special integer.
Like, 1, 4, 5, 4, 3, 1, 3, 3, 5. 3 appears 3 times.
The solution is easy, just do XOR for all of them.
But, what if n integers instead of 1 occur odd number of times, how you
gonna find them out?
【在 d**e 的大作中提到】
: 我能不能问问这题具体是什么？
: 这些数有范围的吗？是连续的吗？
: 跟那题不见一个数的是不一样吧？
|
f*********u
发帖数: 6298 | |
x****k
发帖数: 2932 | 7 My 2 cents
用bitmap，每个数占用1bit，0表示没出现或者出现偶数次，1表示奇数次。
O（n） time complexity |
c*******t
发帖数: 1095 | |
w*****e
发帖数: 721 | 9 XOR: exclusive or.
for example:
1001 xor 1100 = 0101
(different bit => 1 , same bit => 0)
1 xor 1 =0
1 xor 0 =1 |
l*******o
发帖数: 791 | 10 但是Bitmap到底要申请多大的空间才能合适呢？
如果input是[1,1000000,1000001,10000002,...]怎么办呢？
我觉得还是用map好一点map.规避了申请空间问题上的麻烦，这样好么？
【在 x****k 的大作中提到】
: My 2 cents
: 用bitmap，每个数占用1bit，0表示没出现或者出现偶数次，1表示奇数次。
: O（n） time complexity
|
l****i
发帖数: 396 | 11 这个数组里元素的值有范围么？
有的话，我觉得用bitmap。
没有的话，就不知道了。。。等解答 |
h***n
发帖数: 276 | 12 还是异或(XOR)，出现偶数次的，都消掉了(0)，出现奇数次的保留了下来，因为0^x=x
【在 e*****e 的大作中提到】
: 地球人都知道如果只有一个整数咋办。XOR~~~~~
: 如果是n个整数出现奇数次,怎么搞？
|
l****i
发帖数: 396 | 13 保留下来的是几个出现奇数次的数的xor值，怎么把每个都找出来呢？
x
【在 h***n 的大作中提到】
: 还是异或(XOR)，出现偶数次的，都消掉了(0)，出现奇数次的保留了下来，因为0^x=x
|
b*******g
发帖数: 355 | 14 如果是32bit int，则512M，不算很过分的空间要求。
如果用map，则avarage time complexity是nlog（n）（如果不对请指正）
在nlog（n）的情况下就不用map了，直接sort后再遍历一边就可以了。
【在 l*******o 的大作中提到】
: 但是Bitmap到底要申请多大的空间才能合适呢？
: 如果input是[1,1000000,1000001,10000002,...]怎么办呢？
: 我觉得还是用map好一点map.规避了申请空间问题上的麻烦，这样好么？
|
