I***A 发帖数: 6 | 1 Given an array A of n elements and an integer k (where k
]...A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort
the array A in O(n) time and O(1)space
有没有人可以指导一下? |
c****p 发帖数: 6474 | 2 这题现在都成悬案了
[0
【在 I***A 的大作中提到】 : Given an array A of n elements and an integer k (where k: ]...A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort : the array A in O(n) time and O(1)space : 有没有人可以指导一下?
|
d*******l 发帖数: 338 | 3 这题的一个特例就是那个把a1 a2 ..an b1 b2 .. bn变成a1 b1 a2 b2 .. an bn的题。
那题要求inplace不是没人给出O(n)的办法么,这题的普遍情况应该复杂的多。 |
f*******t 发帖数: 7549 | 4 有可以算作O(n)的解法
http://www.mitbbs.com/article/JobHunting/31948939_0.html
【在 d*******l 的大作中提到】 : 这题的一个特例就是那个把a1 a2 ..an b1 b2 .. bn变成a1 b1 a2 b2 .. an bn的题。 : 那题要求inplace不是没人给出O(n)的办法么,这题的普遍情况应该复杂的多。
|
d*******l 发帖数: 338 | 5 看过那个解法,确实很巧妙。
不过那里面也说如果算上计算index应该不止O(n)。这题就更没规律了,或许没有O(n)
inplace的算法也说不定。
【在 f*******t 的大作中提到】 : 有可以算作O(n)的解法 : http://www.mitbbs.com/article/JobHunting/31948939_0.html
|
I***A 发帖数: 6 | 6 好像有篇论文是专门将这个问题的; 感觉这个问题有点难度; |
b*****c 发帖数: 1103 | |