e***s
发帖数: 799 | 1 两个sorted数组，其中一个后面有很多空足以放下前面一个，merge它们。尽可能加
上各种错误检查
如果有n个sorted数组，其中一个很大可以放下其他的n-1个。如何merge，如何改进
我的办法是把空间打的那个数组的元素挪到数组尾，然后再merge。有没有比较好的办
法？ |
z****c
发帖数: 602 | |
e***s
发帖数: 799 | 3 一语惊醒梦中人。
【在 z****c 的大作中提到】
: 从尾部开始merge
|
e***s
发帖数: 799 | 4 请问这个“如何改进”怎么回答？
【在 z****c 的大作中提到】
: 从尾部开始merge
|
y*****n
发帖数: 243 | 5 indeed merge them from the end.
if there are n of them, I think we can use k way merge. use an heap to
store all tail element, every time pop the maxmum and store it in the
biggest array.
Any better ideas? |
H*****1
发帖数: 4815 | 6 两个的话，就是从两个数组末尾开始比较，最大的放在剩余空间的末尾
多个的话可以用一个max heap来存所有的数组的当前最大元素，每次把最大的放在剩余
空间的末尾
【在 e***s 的大作中提到】
: 两个sorted数组，其中一个后面有很多空足以放下前面一个，merge它们。尽可能加
: 上各种错误检查
: 如果有n个sorted数组，其中一个很大可以放下其他的n-1个。如何merge，如何改进
: 我的办法是把空间打的那个数组的元素挪到数组尾，然后再merge。有没有比较好的办
: 法？
|
e***s
发帖数: 799 | 7 FOR n个sorted array,我的想法是：
奇数次，merge from the end.
偶数次，merge from the beginning. |
b***k
发帖数: 77 | 8 Every 2 arrays need to be merged if there are N arrays. The space that need
to store the result will need to be alternated between small arrays and the
large array. |
