n*w
发帖数: 3393 | 1 这个题怎么解？
Yash is a student at MIT and has to do a lot of work. He has finished k
homeworks and the deadlines of these homeworks lie between 0 to 𝑘^2
- 1.
Help Yash sort these homeworks in non-decreasing order of deadlines with
expected time and space complexity O(k).
Test Case 1:
Input: k = 5, homeworks = [13, 24, 1, 17, 8]
Output: [1, 8, 13, 17, 24]
https://algomart.quora.com/?__ni__=0&__tiids__=34496228&__filter__=all&__
nsrc__=notif_page&__sncid__=17590302065&__snid3__=24647767134#anchor |
h****r
发帖数: 258 | 2 将这些数字看成n进制，使用radix-sort.
The running time is O(4n) = O(n)
The radix sort running time is O(d * (n + k)) , where d is the number of
digit, n is the number of elements, and k is the number of possible values.
In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n
) = O(n) |
B********u
发帖数: 1 | 3 radix是O(k^2)吧，k个数，每个数字k位
4n
【在 h****r 的大作中提到】
: 将这些数字看成n进制，使用radix-sort.
: The running time is O(4n) = O(n)
: The radix sort running time is O(d * (n + k)) , where d is the number of
: digit, n is the number of elements, and k is the number of possible values.
: In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n
: ) = O(n)
|
C*****l
发帖数: 1 | 4 bucket sort, take sqrt firstly, which gives bucket。 在每个bucket里面再sort
一下，因为只有k个，所以k个bucket每个bucket里面average个数应该是1. Worsecase
都在一个bucket里面，需要看klog（k)再sort一下 |
B********u
发帖数: 1 | 5 我也想了一个解:
先对每个数取log_2()，然后counting sort，从1到k，按照hashtable建立各个bucket
chain，这样期望的时间空间复杂度应该都是O(k) |
C*****l
发帖数: 1 | 6 取log_2可能会拥挤在少数bucket里面，按照题设应该是sqrt
bucket
【在 B********u 的大作中提到】
: 我也想了一个解:
: 先对每个数取log_2()，然后counting sort，从1到k，按照hashtable建立各个bucket
: chain，这样期望的时间空间复杂度应该都是O(k)
|
B********u
发帖数: 1 | 7 没毛病，像hashtable那样放个linkedlist就好了
反正这些list期望长度都是1
update:跟你的一样吧，取sqrt的问题是不是还剩2^{k/2}个bucket，还是太多了
【在 C*****l 的大作中提到】
: 取log_2可能会拥挤在少数bucket里面，按照题设应该是sqrt
:
: bucket
|
C*****l
发帖数: 1 | 8 取值范围(0, 𝑘^2- 1)， sqrt之后（0，k), 如果是log2的话（0， 2*log2（K
))
, log2(k) << k when k is large，所以可能时间复杂度满足要求。
【在 B********u 的大作中提到】
: 没毛病，像hashtable那样放个linkedlist就好了
: 反正这些list期望长度都是1
: update:跟你的一样吧，取sqrt的问题是不是还剩2^{k/2}个bucket，还是太多了
|
B********u
发帖数: 1 | 9 我傻逼了，看成了2^k
（K
【在 C*****l 的大作中提到】
: 取值范围(0, 𝑘^2- 1)， sqrt之后（0，k), 如果是log2的话（0， 2*log2（K
: ))
: , log2(k) << k when k is large，所以可能时间复杂度满足要求。
|
