e*8
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.
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
3 楼
可是 counting 的话是 O(K) space ...
e*8
4 楼
k is a constant by assumption
【在 h*****7 的大作中提到】
: 可是 counting 的话是 O(K) space ...
【在 h*****7 的大作中提到】
: 可是 counting 的话是 O(K) space ...
s*n
5 楼
O(1) 吧， 你就直接操作数组本身呀， A[i-1]=i 不就行了，
【在 h*****7 的大作中提到】
: 可是 counting 的话是 O(K) space ...
f*4
6 楼
只是k个不同的数字，而不是1～K之间的？
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
o*n
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
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
8 楼
这题好像还是我几年前贴的，其实就是荷兰国旗问题扩展
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
g*9
9 楼
请大牛给个思路吧？
【在 P*******7 的大作中提到】
: 这题好像还是我几年前贴的，其实就是荷兰国旗问题扩展
【在 P*******7 的大作中提到】
: 这题好像还是我几年前贴的，其实就是荷兰国旗问题扩展
x*o
10 楼
是n*klogk?
【在 h*****7 的大作中提到】
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
: 没有想出来，求指点
相关阅读
公司是不是嫌我太烦了?从developer转到QA? (转载)有过往工作经验无专业相关经验可行吗help on Excel question 批处理文件请教Infosys这个公司怎么样？annual commission是啥意思？这样的job description 怪吗CPT回国实习电面后一般多久有消息？Knapsack O(n) space存RP，谈谈找工作的经历LD拿到offer了这个公司在狂招人去大公司or小公司?请大家帮我看看这句话是什么意思？ 有希望吗？这是不是个面试机会，如何回email (谢谢）这里有没有H4身份没有EAD但成功找到工作的？焦急：能否推荐一下各行各业的简历模板和修改简历的网站呢careerbuilder resume upgrade, is it worth it?周四ernst young面试结束，还不错