p******n 发帖数: 32 | 1 一些面经那个帖子里的一道题
一个数组有k个不同数字,假设k是常数,如何O(n) time, O(1)space排序 |
m**k 发帖数: 290 | 2 My guess
First pass: count frequency
create an array, occur[k][2], occur[i][0] is the i-th unique number, occur
[i][1] is the frequency of this number.
time n, space 2xk
Second pass: sort
sort the array occur[k][2] with occur[i][0] as the key
time O(klogk)
Third pass: restore the sorted array
for i in 0:k-1
for j in 0:occur[i][1]
array[n++] = occur[i][0]
time n
Overall time 2n + O(klogk) = O(n), overall space 2xk = O(1) |
y*c 发帖数: 904 | 3
这道题就是couting sort的in place 变种。counting好知道该放的位置之后,就是一
个juggling的过程。从后往前scan,碰到位置不对的,就放到该放的位置,然后循环。
【在 p******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一些面经那个帖子里的一道题 : 一个数组有k个不同数字,假设k是常数,如何O(n) time, O(1)space排序
|
P*******7 发帖数: 55 | 4 You can only do one pass instead of several passes...
【在 y*c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这道题就是couting sort的in place 变种。counting好知道该放的位置之后,就是一 : 个juggling的过程。从后往前scan,碰到位置不对的,就放到该放的位置,然后循环。
|
s*******s 发帖数: 46 | 5 觉得如果O(1)的话很难做到one pass
several很简单 |
y*c 发帖数: 904 | 6
Why is that? It reads O(n). Do you have one pass algorithm for this problem?
【在 P*******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You can only do one pass instead of several passes...
|
P*******7 发帖数: 55 | 7 Similar to the problem with only two different values, we can extend that
algorithm to the problem with a constant number of different values with
one pass.
A special case with three different values is called "Dutch National Flag
Problem". http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
You may start from there.
problem?
【在 y*c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : Why is that? It reads O(n). Do you have one pass algorithm for this problem?
|
y*c 发帖数: 904 | 8
I am interested in the fancy name but found it nothing but the "partition"
algorithm. Given K possible values, you need O(Kn) worst case even though it
is "one pass".
【在 P*******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Similar to the problem with only two different values, we can extend that : algorithm to the problem with a constant number of different values with : one pass. : A special case with three different values is called "Dutch National Flag : Problem". http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/ : You may start from there. : : problem?
|
p******n 发帖数: 32 | 9 Aglee. It is not worth using the "partition" algorithm when k > 3.
Counting algorithm is better in the sense of time complexity. In
addition, the code is more clean.
"partition"
though it
【在 y*c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : I am interested in the fancy name but found it nothing but the "partition" : algorithm. Given K possible values, you need O(Kn) worst case even though it : is "one pass".
|