f**********t
发帖数: 1001 | 1 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
还有更好的方法没？非常感谢 :) |
a*********0
发帖数: 2727 | 2 n-way merge
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
|
f**********t
发帖数: 1001 | |
f**********t
发帖数: 1001 | 4 有没有更好的做法？
Brute force method:
sort the array using any existed sort algorithm, just treating the array as
normal array. The best time complexity is O(nlogn)
Method2:
Among M sorted array, select the smallest number from one array, move the
pointer to the next integer of the array. repeat this routine, until all
integers are put into order.
For each integer in the output array, it's compared M times. the time
complexity is O(n*M)
The code is listed below:
void nwaymergesort(int* arr, int* out, int M,int n)
{
//record the current position for each sorted array
int *pos = new int[M];
//initialize position
for(int i=0;i
pos[i]=i;
for(int j=0;j
int min = -1;
int k = -1;
for(int i=0;i
if(pos[i]
we should jump this array
if(min == -1 || arr[pos[i]]
min = arr[pos[i]];
k = i;
}
}
}
out[j]=min;
pos[k]+=M;
}
} |
h**********d
发帖数: 4313 | 5 用heap
【在 f**********t 的大作中提到】
: 有没有更好的做法？
: Brute force method:
: sort the array using any existed sort algorithm, just treating the array as
: normal array. The best time complexity is O(nlogn)
: Method2:
: Among M sorted array, select the smallest number from one array, move the
: pointer to the next integer of the array. repeat this routine, until all
: integers are put into order.
: For each integer in the output array, it's compared M times. the time
: complexity is O(n*M)
|
f**********t
发帖数: 1001 | 6 嗯，heap确实比上面的method 2好。
【在 h**********d 的大作中提到】
: 用heap
|
s********v
发帖数: 288 | 7 sort k个
然后k个一起排序：）
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
|
a*********0
发帖数: 2727 | 8 it's still n-way merge with the aid of min-heap. O(nlogk)complexity
【在 f**********t 的大作中提到】
: 嗯，heap确实比上面的method 2好。
|
f**********t
发帖数: 1001 | 9 对。
Min-heap O(nlogk)
method 2那个O(nk)
【在 a*********0 的大作中提到】
: it's still n-way merge with the aid of min-heap. O(nlogk)complexity
|
f**********t
发帖数: 1001 | 10 这里假设k个数组已经有序
【在 s********v 的大作中提到】
: sort k个
: 然后k个一起排序：）
|
h**********d
发帖数: 4313 | 11 I think it's O(nklogk) :)
【在 a*********0 的大作中提到】
: it's still n-way merge with the aid of min-heap. O(nlogk)complexity
|
n*******n
发帖数: 3 | 12 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk)， n为所有
integer的个数. 证明如下：
一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组，每组分别
sort，再合起来，不可能比O(nlogn)更快。 n ＝ k * m
分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
数组的时间不可能小于 O（nlogn）- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
楼上各位已经找到最优解了。 |
i**********e
发帖数: 1145 | 13 Time complexity: O(N log k), N = total elements of all arrays, k = total
number of arrays.
Space complexity: O(k), to record the indices of each array.
Tips: Use a vector of vectors instead of 2d arrays to reduce coding complexity :)
typedef pair Pair;
vector mergeKSortedArrays(vector > A) {
int k = A.size();
priority_queue, greater > q;
vector ret;
int *index = new int[k];
for (int i = 0; i < k; i++) {
q.push(Pair(A[i][0], i));
index[i] = 1;
}
while (!q.empty()) {
Pair p = q.top();
q.pop();
ret.push_back(p.first);
if (index[p.second] < A[p.second].size()) {
q.push(Pair(A[p.second][index[p.second]], p.second));
index[p.second]++;
}
}
delete[] index;
return ret;
} |
b*******8
发帖数: 37364 | 14 CRLS后习题讨论过这个。如果独立想出来的，还是很牛啊。
【在 n*******n 的大作中提到】
: 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk)， n为所有
: integer的个数. 证明如下：
: 一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组，每组分别
: sort，再合起来，不可能比O(nlogn)更快。 n ＝ k * m
: 分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
: 数组的时间不可能小于 O（nlogn）- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
: 楼上各位已经找到最优解了。
|
