Y******l
发帖数: 19 | 1 Given an array of N integers from range ［0, N] and one is missing. Find the
missing number.
1) how to find the missing number if the element of array is integer value
2) if the element of the array is a bit vector, presenting the integer
number. for example, 000 --> 0, 010 --> 2. |
p*****2
发帖数: 21240 | 2
the
第一问求和吧。第二问亦或吧。
【在 Y******l 的大作中提到】
: Given an array of N integers from range ［0, N] and one is missing. Find the
: missing number.
: 1) how to find the missing number if the element of array is integer value
: 2) if the element of the array is a bit vector, presenting the integer
: number. for example, 000 --> 0, 010 --> 2.
|
b******g
发帖数: 1721 | 3 for the second, transform the presentation from a bit vector to an integer, and then run the first algorithm.
For the xor operation, does that require the N should be equal to 2^m or just any integer number? |
Y******l
发帖数: 19 | 4
, and then run the first algorithm.
just any integer number?
是啊，我也有同样的疑问，如果N不是2^m.. 有什么快速的方法吗？
【在 b******g 的大作中提到】
: for the second, transform the presentation from a bit vector to an integer, and then run the first algorithm.
: For the xor operation, does that require the N should be equal to 2^m or just any integer number?
|
k***t
发帖数: 276 | 5 第一个异或。第二个或（初值零）或者与（初值为up to N bit 全一，与每个element的反）。
, and then run the first algorithm.
just any integer number?
【在 b******g 的大作中提到】
: for the second, transform the presentation from a bit vector to an integer, and then run the first algorithm.
: For the xor operation, does that require the N should be equal to 2^m or just any integer number?
|
p*****2
发帖数: 21240 | 6
a^b^c
a^b
a^b^c^a^b=c^0=c
【在 Y******l 的大作中提到】
:
: , and then run the first algorithm.
: just any integer number?
: 是啊，我也有同样的疑问，如果N不是2^m.. 有什么快速的方法吗？
|
b******g
发帖数: 1721 | 7 nice, so N does not need to be 2^m.
http://www.geeksforgeeks.org/archives/580
has a more detailed example. Hope this helped other guys.
【在 p*****2 的大作中提到】
:
: a^b^c
: a^b
: a^b^c^a^b=c^0=c
|
b******g
发帖数: 1721 | 8 can you explain the second solution a little bit more?
element的反）。
【在 k***t 的大作中提到】
: 第一个异或。第二个或（初值零）或者与（初值为up to N bit 全一，与每个element的反）。
:
: , and then run the first algorithm.
: just any integer number?
|
|
t****y
发帖数: 27 | 9 For the second question, do XOR with 1..N bit by bit should be fine
the
【在 Y******l 的大作中提到】
: Given an array of N integers from range ［0, N] and one is missing. Find the
: missing number.
: 1) how to find the missing number if the element of array is integer value
: 2) if the element of the array is a bit vector, presenting the integer
: number. for example, 000 --> 0, 010 --> 2.
|
