avatar
一个小公司面经# JobHunting - 待字闺中
B*p
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
有大牛给说说没?
avatar
i*r
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
avatar
l*q
3
如果k是一个常数的话,就是O(1)的空间啊。。。。哈哈
avatar
l*q
4
如果k是一个常数的话,就是O(1)的空间啊。。。。哈哈
avatar
y*c
5
merge from end
avatar
s*t
6
但是好像每步都要shift吧,
这样的话,时间复杂度就不是O(n)了吧。
如果是list的话,就对了。

【在 y*c 的大作中提到】
: merge from end
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。