电面遇到一个没见过的排序算法

buaawj 发表于 2015-7-9 06:52
请问是google的店面题吗? 楼上sliding window + heap 是正解！

Amazon的

xujun 发表于 2015-7-9 01:03
如果第一个数是最大的数，你这个算法是必然会排到最后的。

不会的，第一个数一定在0到k之间

mayijie88 发表于 2015-7-9 05:53
这是典型的insertion sort, 复杂度可以做到O(n*k)，可以看一下它的wiki，并且insertion sort是online sorti ...

是的，每个位置的移动范围小于k，是条件

shuishuimiao 发表于 2015-7-9 01:57
好像是那个geeksforgeeks上的那个k sorted array排序， 题目是意思是input的数组本身就满足排序之后每个 ...

果然是这道题
http://www.geeksforgeeks.org/nearly-sorted-algorithm/

Thx！

谢谢 Shuishuimiao 指出，这个是geeksforgeeks上的那个k sorted array排序题

谢谢 Shuishuimiao 指出，这个是geeksforgeeks上的那个k sorted array排序题  http://www.geeksforgeeks.org/nearly-sorted-algorithm/

谢谢 shuishuimiao 指出，这个是geeksforgeeks上的那个k sorted array排序 http://www.geeksforgeeks.org/nearly-sorted-algorithm/   用Insert sort 复杂度是O(n*k), 用最小堆是O(n*logk)

昨天 无人店 公司  语音组面到了，这么老的题，lc lt为啥都没收录？