h*****7
发帖数: 103 | 1 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
没有想出来，求指点 | e*******8
发帖数: 94 | 2 counting sort...
if we don't require the sorting to be stable, we don't need to use an
auxiliary array of size O(n); just an array of size O(k) = O(1) is
sufficient. | h*****7
发帖数: 103 | 3 可是 counting 的话是 O(K) space ... | e*******8
发帖数: 94 | 4 k is a constant by assumption
【在 h*****7 的大作中提到】
: 可是 counting 的话是 O(K) space ...
| s*******n
发帖数: 305 | 5
O(1) 吧， 你就直接操作数组本身呀， A[i-1]=i 不就行了，
【在 h*****7 的大作中提到】
: 可是 counting 的话是 O(K) space ...
| f*******4
发帖数: 64 | 6 只是k个不同的数字，而不是1～K之间的？
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
| o*****n
发帖数: 189 | 7 a=[22,3,556,223,56556,23,2,767,0, 55, 19,200,300,452,95]
m=max(a) +1
count=[0] * m
for i in a:
count[i]=1
for j in range(m):
if count[j] ==1: print j | P*******7
发帖数: 55 | 8 这题好像还是我几年前贴的，其实就是荷兰国旗问题扩展
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
| g***9
发帖数: 159 | 9 请大牛给个思路吧？
【在 P*******7 的大作中提到】
: 这题好像还是我几年前贴的，其实就是荷兰国旗问题扩展
| x****o
发帖数: 29677 | 10
是n*klogk?
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
|
|
