b*****i
发帖数: 262 | 1 看到以前的面经，里面有这么道题，请问有什么思路？ |
g*****x
发帖数: 799 | |
f*******4
发帖数: 1401 | 3 +1
【在 g*****x 的大作中提到】
: n-way merge sort吧
|
l****i
发帖数: 396 | 4 +1 ....
【在 f*******4 的大作中提到】
: +1
|
J*********n
发帖数: 370 | 5
this really doesn't make too much sense since you will have to maintain a
heap to retrieve the max element among the n elements, which turns out
to be O(nlgn). But without knowing A[i] < A[n+i], we can also achieve this
by some sorting algorithms.
Unless there is a quicker method to retrieve the max element, I don't see
the value of having this property.
【在 g*****x 的大作中提到】
: n-way merge sort吧
|
P********l
发帖数: 452 | 6 http://www.sureinterview.com/shwqst/558001
It is shell sort half way done. So, continue the shell sort until the step
length (N) is 1.
n-way sort is hard to be done in-place, but it is faster. |
h**k
发帖数: 3368 | 7 复杂度是O(mlgN)，m是数组长度，N是条件里的a(i)
于m的线性算法。
【在 J*********n 的大作中提到】
:
: this really doesn't make too much sense since you will have to maintain a
: heap to retrieve the max element among the n elements, which turns out
: to be O(nlgn). But without knowing A[i] < A[n+i], we can also achieve this
: by some sorting algorithms.
: Unless there is a quicker method to retrieve the max element, I don't see
: the value of having this property.
|
c******n
发帖数: 4965 | 8 简单。 just view them as N separate lists, each of which is completely
sorted. you just pick one for every N element.
【在 b*****i 的大作中提到】
: 看到以前的面经，里面有这么道题，请问有什么思路？
|
