g*******s
发帖数: 490 | 1 对于一个missing number的题目，用xor是最好解法
比如，1，2，3，5，missing number is 4
(0^1^2^3^4^5) ^ (1^2^3^5) = 4
xor 1-n的数，再xor array里面的数给你那个唯一的missing number
但是这招对于2个或以上missing number行不通
所以我们回到addition to find missing number的路上来
sum(1-n) - sum(elements in array) 也可以给你唯一的missing number (potential
overflow problem)
把那个方法generalize到>1个missing number
a1=sum(1-n) - sum(elements in array), a1是missing number的和
a2=sum(1 squre-n squre) - sum (elements squre in array)， a2是missing number
的平方和
假设两个missing number是x, y
x+y=a1
x squre + y squre = a2
解方程得解
如果有k个missing number, 求到k次方的和
所以这个本质上变成求方程组解的问题。
这一类的方程组可以转化成求x的一元k次方程，系数是elementary symmetric
polynomials。然后用迭代求k个根。
anyway。。。说到最后，还是用bitmap之类的来找多个missing number(s)好了 |
l*****a
发帖数: 14598 | 2 谁说2个数不行？
看着
假定a,b are lost
after the operation as what u did below,
the result will be a^b,a!=b,so there must have at least one bit
that a!=b on that bit,
then divide the group of number into two groups by that bit
then a,b will be in different group
obviously,a,b will be 1 missing number in different group
then do the same operation for the 2 groups.
(potential
【在 g*******s 的大作中提到】
: 对于一个missing number的题目，用xor是最好解法
: 比如，1，2，3，5，missing number is 4
: (0^1^2^3^4^5) ^ (1^2^3^5) = 4
: xor 1-n的数，再xor array里面的数给你那个唯一的missing number
: 但是这招对于2个或以上missing number行不通
: 所以我们回到addition to find missing number的路上来
: sum(1-n) - sum(elements in array) 也可以给你唯一的missing number (potential
: overflow problem)
: 把那个方法generalize到>1个missing number
: a1=sum(1-n) - sum(elements in array), a1是missing number的和
|
l*****a
发帖数: 14598 | 3 3个数的话
想办法分成两组，一组一个missing一组两个missing
then...
potential
【在 g*******s 的大作中提到】
: 对于一个missing number的题目，用xor是最好解法
: 比如，1，2，3，5，missing number is 4
: (0^1^2^3^4^5) ^ (1^2^3^5) = 4
: xor 1-n的数，再xor array里面的数给你那个唯一的missing number
: 但是这招对于2个或以上missing number行不通
: 所以我们回到addition to find missing number的路上来
: sum(1-n) - sum(elements in array) 也可以给你唯一的missing number (potential
: overflow problem)
: 把那个方法generalize到>1个missing number
: a1=sum(1-n) - sum(elements in array), a1是missing number的和
|
g*******s
发帖数: 490 | 4 挺好的，找到 most significant bit which is 1,然后再走一遍
【在 l*****a 的大作中提到】
: 谁说2个数不行？
: 看着
: 假定a,b are lost
: after the operation as what u did below,
: the result will be a^b,a!=b,so there must have at least one bit
: that a!=b on that bit,
: then divide the group of number into two groups by that bit
: then a,b will be in different group
: obviously,a,b will be 1 missing number in different group
: then do the same operation for the 2 groups.
|
g*******s
发帖数: 490 | 5 3个数和以上应该行不通了，因为1的bit位未必是他们不同的bit位
比如 1^1^1 ＝ 1
反过来，0的bit位也可以是他们不同的bit位
0^1^1=0
【在 l*****a 的大作中提到】
: 3个数的话
: 想办法分成两组，一组一个missing一组两个missing
: then...
:
: potential
|
l*****a
发帖数: 14598 | 6 find the biggest one in the array
for each bit,it can be 0 or 1
divide the group based on that until u can find there are 1 missing number
in one group and 2 in another group
it is impossible that each time 3 different numbers are in the same group
if so,the 3 numbers should be the same
【在 g*******s 的大作中提到】
: 3个数和以上应该行不通了，因为1的bit位未必是他们不同的bit位
: 比如 1^1^1 ＝ 1
: 反过来，0的bit位也可以是他们不同的bit位
: 0^1^1=0
|
g*******s
发帖数: 490 | 7 没看懂
【在 l*****a 的大作中提到】
: find the biggest one in the array
: for each bit,it can be 0 or 1
: divide the group based on that until u can find there are 1 missing number
: in one group and 2 in another group
: it is impossible that each time 3 different numbers are in the same group
: if so,the 3 numbers should be the same
|
g*****k
发帖数: 623 | 8 How do you test if there is only one missing number?
And what is the complexity of this algorithm?
【在 l*****a 的大作中提到】
: find the biggest one in the array
: for each bit,it can be 0 or 1
: divide the group based on that until u can find there are 1 missing number
: in one group and 2 in another group
: it is impossible that each time 3 different numbers are in the same group
: if so,the 3 numbers should be the same
|
l*****a
发帖数: 14598 | 9 for the group after divided
do the same operation,if the result is 0,then no missing in this group
otherwise,divide again,for the two groups,it could be 1 missing+1 missing
or 1 missing+no missing
pay attention we divide the whole group each time,so it should be O(N)
for 1 loop
then the whole time complexity should be Log2M*O(N)
M is the value of the biggest number
【在 g*****k 的大作中提到】
: How do you test if there is only one missing number?
: And what is the complexity of this algorithm?
|
g*****k
发帖数: 623 | 10 It is easy to test if there is no missing in the group.
I'm just curious about how do you know you are missing one,
but not missing two? Would you pre-compute the desired number in each group?
And also count the number while you divide the original group.
【在 l*****a 的大作中提到】
: for the group after divided
: do the same operation,if the result is 0,then no missing in this group
: otherwise,divide again,for the two groups,it could be 1 missing+1 missing
: or 1 missing+no missing
: pay attention we divide the whole group each time,so it should be O(N)
: for 1 loop
: then the whole time complexity should be Log2M*O(N)
: M is the value of the biggest number
|
l*****a
发帖数: 14598 | 11 do it for the second time if u know it isn't no missing
group?
【在 g*****k 的大作中提到】
: It is easy to test if there is no missing in the group.
: I'm just curious about how do you know you are missing one,
: but not missing two? Would you pre-compute the desired number in each group?
: And also count the number while you divide the original group.
|
