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. |