B*****p
发帖数: 339 | 1 问了些背景,和做过的project,
然后,这个没有搭号,就fail 了
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
有大牛给说说没? |
i**r
发帖数: 40 | 2 I don't think there is an answer.
The problem is exactly the last step of merge sort, i.e merging the sorted
first half and the sorted second half of the array. I doubt there is O(n) time in-place
algorithm for merging with array. Otherwise merge sort will not need O(n) space.
The problem should be easy if the container is a linked list instead of an array.
Are you sure you get the question right? or may be the interviewer was just
try to test you?
Good luck |
l****q
发帖数: 177 | 3 如果k是一个常数的话，就是O(1)的空间啊。。。。哈哈
逃 |
l****q
发帖数: 177 | 4 如果k是一个常数的话，就是O(1)的空间啊。。。。哈哈
逃 |
y*c
发帖数: 904 | |
s*******t
发帖数: 248 | 6 但是好像每步都要shift吧，
这样的话，时间复杂度就不是O(n)了吧。
如果是list的话，就对了。
【在 y*c 的大作中提到】
: merge from end
|
