G**********s
发帖数: 70 | 1 An array A[1...n] contains all the integers from 0 to n except for one
number which is
missing. In this problem, we cannot access an entire integer in A with a
single operation.
The elements of A are represented in binary, and the only operation we can
use to access
them is “fetch the jth bit of A[i]”, which takes constant time. Write code
to find the
missing integer. Can you do it in O(n) time? | G**********s
发帖数: 70 | 2 应该是和column sum 有关，但是我没有看出来规律阿 | f****4
发帖数: 1359 | | r*******u
发帖数: 185 | | H*X
发帖数: 281 | 5 我不明白这道题, 为什么不可以当成普通的算法做, 一个integer的长度是固定的, 如
果fetch一个bit是constant,那么比如说一个32bits的integer,我把每个bits都fetch一
边也是constant,那样只要针对每个integer,把bit都读出来,加一起, 就得到这个
integer的值了,这就和把所有a[i]加一起然后对比sum的算法一样了
career cup的解法是算column sum,运算的时间是一样的,也都是要吧所有的bit加一起
啊 | s*******r
发帖数: 197 | 6 我对careerup的解法有个疑问，
书上说Let’s assume that n is one less than a power of two (eg, n = 2^k - 1)
. If it’s not, it can be padded
with no more than n/2 values to make it so.
这里如何pad呢，比如n是奇数的时候？
【在 f****4 的大作中提到】
: 参见careercup pdf
| z*********3
发帖数: 37 | 7 这里的意思是把已有的数扩大到最近的2的power减一的数
比如是5，就扩大到7
是12，就扩大到15
这样就能直接比较每一位0和1的个数了
1)
【在 s*******r 的大作中提到】
: 我对careerup的解法有个疑问，
: 书上说Let’s assume that n is one less than a power of two (eg, n = 2^k - 1)
: . If it’s not, it can be padded
: with no more than n/2 values to make it so.
: 这里如何pad呢，比如n是奇数的时候？
| v********w
发帖数: 136 | 8 同感
【在 H*X 的大作中提到】
: 我不明白这道题, 为什么不可以当成普通的算法做, 一个integer的长度是固定的, 如
: 果fetch一个bit是constant,那么比如说一个32bits的integer,我把每个bits都fetch一
: 边也是constant,那样只要针对每个integer,把bit都读出来,加一起, 就得到这个
: integer的值了,这就和把所有a[i]加一起然后对比sum的算法一样了
: career cup的解法是算column sum,运算的时间是一样的,也都是要吧所有的bit加一起
: 啊
| s*******r
发帖数: 197 | 9 有道理，不过我觉得书上的解法还是有点问题，严格来说不算O(N)，算O(N*lg（n））
因为k=logN，对吗
【在 z*********3 的大作中提到】
: 这里的意思是把已有的数扩大到最近的2的power减一的数
: 比如是5，就扩大到7
: 是12，就扩大到15
: 这样就能直接比较每一位0和1的个数了
:
: 1)
|
|
