w***g
发帖数: 5958 | 1 一个数列排序。已知每个数在原数列中的位置和排完序后的位置相差不超过K位。如何设
计排序算法。
昨天被面的。在给出证明算法正确时相当地纠结了一阵。 | a****o
发帖数: 686 | | a****o
发帖数: 686 | 3 The key invariant is to show that after every iteration of the loop, the
heap contains the smallest element in every list. (omit a formal induction
proof, as the question only asked you to devise an algorithm.) Notice that
each EXTRACT-MIN and INSERT operation requires O(lg k) time, since there are
never more than 2k elements in the heap. The loop requires only a constant
amount of other work, and is repeated n times, resulting in O(nlg k) running
time. | s*w
发帖数: 729 | 4 more details:
sorted lists are as:
1,2k+1,4K+1,...
2,2k+2,4k+2,...
...
2k,2k+2k,4k+2k...
total 2k lists to merge
so o(nlogk) with n as total # of elements | a****o
发帖数: 686 | 5 the algorithm requires no merge. and i'm not sure if your method works.
【在 s*w 的大作中提到】
: more details:
: sorted lists are as:
: 1,2k+1,4K+1,...
: 2,2k+2,4k+2,...
: ...
: 2k,2k+2k,4k+2k...
: total 2k lists to merge
: so o(nlogk) with n as total # of elements
|
|
