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排序
: 没有想出来，求指点
相关阅读
有接wechat app 开发的吗？版上大牛们说说ads还有前途吗问一个题 house paintbig bang theory里那个小印算是stereotype么 (转载)On site以后不联系了是个什么情况？Job opening: SDE II plus in Microsoft, Bellevue, WA新老工作overlapping如果要找现公司match，最好是什么时机？手上有专利的看过来 (转载)基金data analyst/developer internal referral，德州印度阿三即将占领中国职场 (转载)以后不说“印度人”，直接说“阴毒人” (转载)有面过MS data scientist的同学吗?太吓人啦!微软总部发生强奸案onsite以后大概多久没回音就可以moveon了？提供Google内推求职求内推：嵌入式软硬件工程师（地点不限），本人现住Rochester-NY长期提供yahoo工作refer为什么十年前台湾人在硅谷压着印度人打 (转载)问一道题(2)