logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
一道比较特别的排序题。求思路求解答。。
avatar
一道比较特别的排序题。求思路求解答。。# JobHunting - 待字闺中
i*7
1 楼
given an array of n unsorted integers and each number is at most k positions
away from its final sorted position, give an efficient sorting algorithm.
avatar
h*t
2 楼

positions
nlogk 复杂度算法.

【在 i*********7 的大作中提到】
: given an array of n unsorted integers and each number is at most k positions
: away from its final sorted position, give an efficient sorting algorithm.
avatar
l*c
3 楼
void kAwaySort(int s[], int n)
{
quickSort(0,k-1);
int i = k;
while(imerge(s, i-k, i-1, i) //merge s[i] into the subarray s[i-k,i-1];
i++;
}
avatar
p*e
4 楼
more details?
I can only come up with O(nk) algorithm

algorithm

【在 h****t 的大作中提到】
:
: positions
: nlogk 复杂度算法.
avatar
Z*Z
5 楼
Note k is between 1 and n-1. As k approaching n-1, your algorithm should con
verge to O(n lgn) naturally :)

【在 p***e 的大作中提到】
: more details?
: I can only come up with O(nk) algorithm
:
: algorithm
avatar
p*e
6 楼
I got it. thx!

con

【在 Z*****Z 的大作中提到】
: Note k is between 1 and n-1. As k approaching n-1, your algorithm should con
: verge to O(n lgn) naturally :)
相关阅读
请问resign letter对以后有影响吗？葛军，男，秒杀了52万江苏考生。。来做最后两题吧 (转载)请问industry postdoc可以申请opt延期吗？lg周一google onsite，求祝福SIX SIGMA我的找工作故事#3-找Cleantech VC工作的理由All I need is a job!!!是不是面试人最后说了：thanks for your time 就表示没有戏了急问关于简历很奇怪的面试结果，真是很受打击+FB的面经Sign，被Epic据了紧急求救问下哪找prevailing wage的数据？Chinese-speaking buyer assistant needed immediately: sponsor H1B请问谁有用Skype面试过？问个非典型Background Checking的问题请问OPT电话加急已经argue了一次，还能再argue吗？找工作 统计 包括phone, onsite, email学校的research Prof有permanent的那种吗？是不是都取决于有没
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。