编程时遇到了一个算法问题，已经有了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个数组如何快速合并？ (558) frkstyc 2006-04-24 19:34:12
  • 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