b********e
发帖数: 693 | 1 这个怎么做到? 如果是32位integer的话 如果是做redix sort的话,是不是就可以O(N)了 |
K******g
发帖数: 1870 | 2 这个一般用hash或者bitmap吧，就可以O（N）了
)了
【在 b********e 的大作中提到】
: 这个怎么做到? 如果是32位integer的话 如果是做redix sort的话,是不是就可以O(N)了
|
I**A
发帖数: 2345 | 3 agree with bitmap..
how to do it with hash?
【在 K******g 的大作中提到】
: 这个一般用hash或者bitmap吧，就可以O（N）了
:
: )了
|
b********e
发帖数: 693 | 4 radix sort应该能实现吧
我知道hash是能实现的
【在 K******g 的大作中提到】
: 这个一般用hash或者bitmap吧，就可以O（N）了
:
: )了
|
x****k
发帖数: 2932 | 5 bitmap is a hash without conflict.
【在 I**A 的大作中提到】
: agree with bitmap..
: how to do it with hash?
|
h**e
发帖数: 13 | 6 请详细说一下bitmap的解法。
我有个疑问，sizeof(bitmap)大约是4*128MB，把全部的数映射到这个bitmap，然后遍
历之，打印出所有的数（非0位），这个时间度是O(n)吗？
【在 x****k 的大作中提到】
: bitmap is a hash without conflict.
|
b********e
发帖数: 693 | 7 我觉得要求space 是O(1),表示的就是不能用额外空间,可以用临时变量
这个bitmap, 虽然一个item占一个bit, 但是如果N无穷大,你这个bitmap的空间复杂度,
也就不是O(1)了
【在 I**A 的大作中提到】
: agree with bitmap..
: how to do it with hash?
|
d**e
发帖数: 6098 | 8 应该是的。
第一个loop reset bitmap为0
第二个set 对应位置为1
第三个就输出
系数为常数3，算是O(n)吧。
【在 h**e 的大作中提到】
: 请详细说一下bitmap的解法。
: 我有个疑问，sizeof(bitmap)大约是4*128MB，把全部的数映射到这个bitmap，然后遍
: 历之，打印出所有的数（非0位），这个时间度是O(n)吗？
|
h**e
发帖数: 13 | 9 输出的时候要遍历整个bitmap (128MB个integer), size大于n，能算作O(n)吗？
迷惑中。。。
【在 d**e 的大作中提到】
: 应该是的。
: 第一个loop reset bitmap为0
: 第二个set 对应位置为1
: 第三个就输出
: 系数为常数3，算是O(n)吧。
|
d**e
发帖数: 6098 | 10 谢谢。倒是没想过这个问题，误导大家了，sorry.
还以为是那题说N很大很大。
【在 h**e 的大作中提到】
: 输出的时候要遍历整个bitmap (128MB个integer), size大于n，能算作O(n)吗？
: 迷惑中。。。
|
