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 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;
}
}
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 有没有更好的做法?
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 有没有更好的做法?
: 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)
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 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) .
: 楼上各位已经找到最优解了。
相关阅读
今天遇到的一个面试题大家找校友内推的多不面试疑问github现在融资到第几轮了?有哪个大侠了解关于APPLE TOP SECRET那个组的情况的?请问Database设计题那里刷?大家骑驴找马一般工资要涨多少小声问一下除了微软,其他IT公司的小兵都没single office吗?请教一下,现在FLG的principle engineer / staff engineer是个什么行情?有人给worldventures打工吗?高帅富算算你分了多少$180M问一道题k Sum要据烙印太容易了待业新毕业 ASIC/VLSI 硕士求建议OPT加急被拒,求支招!!!烙印受重用的原因Cisco和Amazon offer 比较,求意见请问接受了offer又反悔后果到底有多严重?过不了简历关,求建议大家上班一般开多远