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 的大作中提到】
: 一些面经那个帖子里的一道题
: 一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序
|
P*******7
发帖数: 55 | 4 You can only do one pass instead of several passes...
【在 y*c 的大作中提到】
:
: 这道题就是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 的大作中提到】
: 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 的大作中提到】
:
: 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 的大作中提到】
: 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 的大作中提到】
:
: 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".
|
