假设存在O(n)的数组合并算法，那么对任意n个数，将每一个数看成一个只有一个元素的数组，由假设，可以在O(n)时间内将其合并成一个有序数组，即排序问题可以在O(n)时间内解决，这与排序问题的时间下界Ω(nlogn)矛盾，故假设不成立，不存在O(n)的数组合并算法。

> 编程时遇到了一个算法问题，已经有了3个想法，但是都比较慢，想让大家帮忙想想更快的方法，万分感谢！
> 问题是这样的：
>     有k个整型数组，每个数组的长度不同，每个数组都以升序排列但有重复。如何将这n个数组合并成一个数组？合并之后的新数组要也要以升序排列，并且没有重复。
> 
> 目前有3个解决方法：
> 1）两个两个数组合并，如果数组A的数和数组B的数相同，两个下标都往下移，如果A数组的大于B数组的，B的下标往下移，A的不变，如果A数组的小于B数组的，则相反。这样两个数组合并用的时间是O(m+n)。但是如果n个的话，弄不好会O(n*n)。
> 2）把这k个数组接在一起，然后将这个新数组快排，最后再从头到尾扫描一遍，把重复的去掉。
> 3）把第一个数组做成堆，以后每个数组往这个堆里插。
> 
> 貌似这3种算法里，第三个最快，可以达到O(nlogn)，但是还不够快，想问问大家有没有接近O(n)的方法？

• Re:n个数组如何快速合并？ (140) guoxi022 2006-04-24 19:56:48
  • Re:n个数组如何快速合并？ (46) guoxi022 2006-04-24 19:58:14
    • 堆已经足够简单了 (50) xfxyjwf 2006-04-24 20:01:55
    • 你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (50) TN 2006-04-24 20:04:48
      • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (26) guoxi022 2006-04-24 20:11:31
        • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (76) TN 2006-04-24 20:13:50
          • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (88) guoxi022 2006-04-24 20:17:02
            • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (50) guoxi022 2006-04-24 20:18:24
• 好象只能 两两合并, ms 2442 是一个 数组合并的题 (49) semonteer 2006-04-24 20:07:51
  • 好像用那个选择树 (0) wywcgs 2006-04-25 09:48:51
  • 他说的是多路归并吧...... (53) ArXoR 2006-04-25 11:33:31