p*****2
发帖数: 21240 | 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. | g**********y
发帖数: 14569 | | b******t
发帖数: 965 | 3 k*N肯定可以解的吧
positions
【在 p*****2 的大作中提到】
: 不知道你们见没见过
: 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.
| c****p
发帖数: 6474 | 4 logk*N
建个k个结点的heap，
先把前k个元素建heap，每次extract一个就加个新的并heapnify。
positions
【在 p*****2 的大作中提到】
: 不知道你们见没见过
: 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.
|
|
