x**y
发帖数: 1086 | 1 找整数数组里面出现奇数次的元素那道题
如果只有一个的话可以用xor
如果有多个或者一个都没有该怎么考虑啊 |
g*********s
发帖数: 1782 | 2 which one?
【在 x**y 的大作中提到】
: 找整数数组里面出现奇数次的元素那道题
: 如果只有一个的话可以用xor
: 如果有多个或者一个都没有该怎么考虑啊
|
f*******4
发帖数: 1401 | |
x**y
发帖数: 1086 | 4 请教一下，具体该怎么处理啊？
【在 f*******4 的大作中提到】
: 如果多个的话还是bitmap来的直接
|
i****c
发帖数: 102 | 5 看integer的数值范围和总数目。
如果数目少但范围大，可用hashmap
如果数目大范围小，可用bitmap
对每个integer，如果bitmap中是0，则设为1；如果为1，则设为0。
最后bitmap中仍为1的就是出现次数为奇数的
【在 x**y 的大作中提到】
: 请教一下，具体该怎么处理啊？
|
x**y
发帖数: 1086 | 6 那简化一下
如果只判断
数组里 没有 或者 有>1个 整数出现奇数次的情况
该如何判断呢？
有什么简单的方法么？
【在 i****c 的大作中提到】
: 看integer的数值范围和总数目。
: 如果数目少但范围大，可用hashmap
: 如果数目大范围小，可用bitmap
: 对每个integer，如果bitmap中是0，则设为1；如果为1，则设为0。
: 最后bitmap中仍为1的就是出现次数为奇数的
|
i****c
发帖数: 102 | 7 可以加一个count，记录bitmap中1的个数。
不知道这种情况，是否有不需要额外内存的方法
【在 x**y 的大作中提到】
: 那简化一下
: 如果只判断
: 数组里 没有 或者 有>1个 整数出现奇数次的情况
: 该如何判断呢？
: 有什么简单的方法么？
|
x**y
发帖数: 1086 | 8 如果用bitmap的话，complexity应该是多少啊
【在 i****c 的大作中提到】
: 看integer的数值范围和总数目。
: 如果数目少但范围大，可用hashmap
: 如果数目大范围小，可用bitmap
: 对每个integer，如果bitmap中是0，则设为1；如果为1，则设为0。
: 最后bitmap中仍为1的就是出现次数为奇数的
|
r******e
发帖数: 80 | 9 use XOR, if the result is 0, then no odd integer. If the result is not 0,
then it has at least one odd integer.
【在 x**y 的大作中提到】
: 那简化一下
: 如果只判断
: 数组里 没有 或者 有>1个 整数出现奇数次的情况
: 该如何判断呢？
: 有什么简单的方法么？
|
x**y
发帖数: 1086 | 10 如果正好是0出现奇数次呢？
而且要判断的是是否有2个以上的整数出现奇数次
有思路么？
【在 r******e 的大作中提到】
: use XOR, if the result is 0, then no odd integer. If the result is not 0,
: then it has at least one odd integer.
|
g***s
发帖数: 3811 | 11 give a sample :
1, 2, 3
xor = 0
0,
【在 r******e 的大作中提到】
: use XOR, if the result is 0, then no odd integer. If the result is not 0,
: then it has at least one odd integer.
|
a***y
发帖数: 547 | 12 assume the result after XOR is T,
then let P = -1 XOR T,
find the occurrence of P in original array.
if P occurs odd times, then only one odd,
otherwise, multiple.
Not sure whether this is the answer.
【在 x**y 的大作中提到】
: 那简化一下
: 如果只判断
: 数组里 没有 或者 有>1个 整数出现奇数次的情况
: 该如何判断呢？
: 有什么简单的方法么？
|
x**y
发帖数: 1086 | |
