将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序_阿里巴巴笔试题

推荐

河湖之恋

答案选A。

就算原有的链表是有序的，合并时还是需要将元素一一比较。

编辑于 2015-02-03 10:44:21 回复(1)

corny813

1. 在每一个链表中取出第一个值，然后把它们放在一个大小为N的数组里，然后把这个数组当成heap建成小(大)根堆。此步骤的时间复杂度为O(N)

2. 取出堆中的最小值(也是数组的第一个值), 然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。此步骤的时间复杂度为O(lg N).

3. 不断的重复步骤二，直到所有的链表都为空。

建堆只建一次，复杂度为O(N)；调整堆MN-1次，复杂度为(MN-1)*O(lg N)。所以为O(MN*lg N)

发表于 2015-08-12 00:37:19 回复(8)

Heap

选A。上面答案都说的不清晰。

其实算法不同结果也不一样。

1、两两合并链表。合并链表复杂度 * 一次合并次数 * 所有合并次数。两两合并的复杂度会指数递增，合并数会指数递减。一共应该是log（N）次。前面的合并复杂度较高。所以一般不采用该方法来合并链表。

2、利用堆来合并，（ O（N） + O（log N * N ）) * M。

先利用最链表第一个数，N个数建立堆，复杂度 O （N）

重构堆，并排序，复杂度 O（logN * N ）

每个链表M个数，上述两步重复M次。结果为

M * （O(N) + O(logN * N)）= O (M * N * logN)

编辑于 2015-03-13 13:58:17 回复(5)

<字节内推>

！！！！！！！！！！@@@@@ 高能预警 @@@@@！！！！！！！！！

你们说的都太复杂，不对！应该是这样的：

1、取每个链表第一个元素，组成一个数组，然后对数组排序：时间复杂度：O(NlogN)

2、然后取排序后数组的第一个节点，作为新链表的第一个节点。

3、从被取出节点的某链表中取出下一个节点，插入到数组中，二叉搜索，时间复杂度O(logN)

4、依次重复2、3步骤，因为剩下(M - 1) * N个节点，大约重复(M - 1) * N次

所以最终的时间复杂度：

O(NlogN) + (M - 1) * N * O(logN)

= M * N * O(logN)

说堆排序的，都散了吧~

发表于 2018-03-28 11:41:51 回复(5)

为你扣下F键

我说一个最简单的想法吧首先，两两合并，时间复杂度O(2m)*(n/2)=O(mn) 然后再两两合并，画出来是个二叉树结构，深度是O(logn) 最终结果就是O(mnlogn)

编辑于 2018-09-07 12:57:33 回复(4)

XyParaCrim

m*n个数排序复杂度是O(m*nlog(m*n))，即O(m*nlogm)+O(m*nlogn).又n个m长度序列已排序，即n*O(mlogm)复杂度，前后相减答案即O(m*nlogn).

发表于 2016-09-25 12:31:37 回复(0)

.牛妹

多路归并可以用堆，胜者树，败者树。他们都是二叉树，每个结点在树中比较的效率达到O(lgn)，总共有N*M个结点，每个结点都需要比较，因此是O（N*M*logN）

这3种树的区别：

堆：其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。

胜者树：每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。

败者树：而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树；在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。

所以总的来说，减少了访存的时间。

发表于 2017-07-17 22:56:39 回复(2)

crackhopper

代入 N=1，不需要排序，凡是非常数的都是错误答案。排除BD

代入 M=1，类似正常排序，NlogN

答案是A

发表于 2018-08-25 11:31:17 回复(0)

黏黏糖

采用堆排序的方法进行合并。

（1）首先取出每个链表的第一个元素放在大小为N的数组中，此处的时间复杂度为O(N)；并调整成为小根堆，调整堆的时间复杂度为O（lgN）

（2）取出数组的第一个元素。将该元素所在链表的下一个元素放在数组的第一个位置，继续调整，使之成为小根堆；

（3）重复（2），如果有一个链表已经为空，则改变数组的大小。

共调整MN-1次，调整堆的时间复杂度为O(M*N*lgN）；建堆的时间复杂度为O(N)；故总的时间复杂度为 O(M*N*lgN）

发表于 2017-05-05 10:07:42 回复(1)

philian

先来看常规的归并排序如何求解复杂度。
将任意两个有序序列（长度分别为NA、NB）进行二分归并，所需时间为线性，O(max(NA,NB))
如果递归基为n==1，那么有
T（n）=2*T（n/2）+O（n）
T（1）=O（1）
其中，O（n）是指将等长的两个有序子序列进行二分归并所需的时间，是线性时间。
联立上述两个方程，再加上由线性推导可得的O（n）=n*O（1），能得到
T（n）/n = T（n/2）/（n/2） + O（1）
设T（n）/n为S（n）
那么就有
S（1）=O（1）
S（n）=S（n/2）+O（1）=S（n/4）+O（2）=...=S（n/(2^k)）+O（k）
由上述二式可得，k=logn时抵达递归基S（1），因此有S（n）=O（logn）
T（n）=n*S（n）=O（nlogn）

回到本题，因为长度为M的子序列都已经有序，就相当于把上述从n到1的递归截了一块儿，截掉了M到1的递归部分，因此需要用总的时间复杂度减掉这被截去的一块儿。
n=N*M，因此如果递归到1，时间复杂度应为O（N*M*log（N*M））
而如果n=M，那么递归到1的时间复杂度为O（M*logM），共有N段这样的子序列，因此加起来需要O（N*M*logM）的时间
前后相减，O（N*M*log（N*M）- N*M*logM）=O（N*M*logN）

发表于 2016-12-19 13:01:29 回复(3)

新玥

两个有序数组合并的复杂度为O(m+n)。m，n分别为两个数组的元素个数。现有N个大小为M的有序列表进行合并。首先两两一组进行合并，共有N/2组，时间复杂度为(M+M)*N/2。一轮合并结束完后剩余N/2个大小为2M的有序数组。再次两两合并，以此类推。总共时间复杂度为2M*N/2+4M*N/4+8M*N/8+....＝M*N*logN

发表于 2018-10-04 12:14:15 回复(0)