a*0
2 楼
n-way merge
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
f*t
3 楼
有链接么？搜索感觉有很多个版本也
f*t
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
for(int j=0;j
int k = -1;
for(int i=0;i
if(min == -1 || arr[pos[i]]
k = i;
}
}
}
out[j]=min;
pos[k]+=M;
}
}
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
for(int j=0;j
int k = -1;
for(int i=0;i
if(min == -1 || arr[pos[i]]
k = i;
}
}
}
out[j]=min;
pos[k]+=M;
}
}
h*d
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 的大作中提到】
: 有没有更好的做法？
: 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
6 楼
嗯，heap确实比上面的method 2好。
【在 h**********d 的大作中提到】
: 用heap
【在 h**********d 的大作中提到】
: 用heap
s*v
7 楼
sort k个
然后k个一起排序：）
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
然后k个一起排序：）
【在 f**********t 的大作中提到】
: 一种是每次两两merge，变成k/2个，k/4个，。。。最终变为1个。
: 还有更好的方法没？非常感谢 :)
a*0
8 楼
it's still n-way merge with the aid of min-heap. O(nlogk)complexity
【在 f**********t 的大作中提到】
: 嗯，heap确实比上面的method 2好。
【在 f**********t 的大作中提到】
: 嗯，heap确实比上面的method 2好。
f*t
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
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
10 楼
这里假设k个数组已经有序
【在 s********v 的大作中提到】
: sort k个
: 然后k个一起排序：）
【在 s********v 的大作中提到】
: sort k个
: 然后k个一起排序：）
h*d
11 楼
I think it's O(nklogk) :)
【在 a*********0 的大作中提到】
: it's still n-way merge with the aid of min-heap. O(nlogk)complexity
【在 a*********0 的大作中提到】
: it's still n-way merge with the aid of min-heap. O(nlogk)complexity
n*n
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) .
楼上各位已经找到最优解了。
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
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;
}
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
vector
int k = A.size();
priority_queue
vector
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
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) .
: 楼上各位已经找到最优解了。
【在 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) .
: 楼上各位已经找到最优解了。
相关阅读
Software Engineer Opening (San Jose, CA)google约这周和我10分钟的电面，这是神马情况？面试完没感觉是好是坏紧急求助：朋友被告plagiarism要被退学律师现在都这样么H1b renewal， H4在国内怎么办？现在才收到google的实习通知G公司的on-site面试一定会给结果吗？OPT加急問題面试一半时间纯聊天，还有戏吗?怎么和公司商量推迟上班的时间？工业界H1B换non－profit H1B要什么手续？关于背景调查诚心请教怎样和老板deal编程之美上的一道递推题？onsite前有必要给面试官发邮件吗？接受offer的问题email附过来的offer能收回吗？是不是没戏了？poineer工作稳吗?