合併未知數組的數量

我的問題是，是否有可能合併（未知數量的數組）到一個數組中。所以我不知道數組的數量完全相同（不像合併兩個數組合並n數組等）簽名：合併未知數組的數量

> int [] merge(int k)//k is number of arrays to be merged into a one 
    > merge them 
    //and so on.. 
    > 
    > return array;

2012-03-30 rena-c

很酷的任務，你有什麼嘗試？ – 2012-03-30 09:47:21

你知道數組的數量。它是K :)。合併時是否有任何規則？ – UmNyobe 2012-03-30 09:48:01

我正在分配數組上distrubited network.they分裂成k個分區，在服務器端進行排序，並在客戶端合併。問題是我不知道要合併的數組＃。 – 2012-03-30 09:51:44

如果知道如何合併2個陣列，則可以合併任何數量的陣列;）不確定

2012-03-30 09:48:45 saadtaame

，合併陣列1與陣列2，合併數組1 + 2與陣列3，將array 1 + 2 + 3與array 4合併，直到你沒有剩下陣列。所有你需要的是一種合併2個數組的方法，以及一個用數組列表調用它的方法，直到列表爲空。

2012-03-30 09:49:18

這將是O（kn^2），比amit提出的k-way合併慢得多。但是再一次 - 看起來你需要知道k使用k-way合併，儘管這種方法很慢，你不需要知道k來實現它。 – Dan 2012-03-30 09:58:43

這個想法出現在我的腦海裏:)但它效率不高。 – 2012-03-30 10:02:41

嗯，我認爲它是O（k * n * log（n）），但效率不是一切：k-way合併效率更高，但我認爲你必須知道k開始。 – 2012-03-30 10:15:49

是的，這是可能的，並且對於k陣列它通常使用大小爲k的優先隊列完成。該隊列包含每個數組中的一個元素（以及用於記憶該元素來自哪個數組的標記）。

最初，隊列由來自每個數組的最小元素填充。然後，您只需從隊列中迭代移除最小元素，並將最後一個最小元素來自的數組添加到隊列中。

假設pqueue的標準堆實現，這會產生O（nlog（k））複雜度。

2012-03-30 09:51:09

雖然可以迭代地合併數組，一個更有效的方式將是一個k-way merge，其在O(nlogk)完成，其中k是陣列的數量和n是元件的總數，使用優先級隊列。

注：它不能做的更好，然後O(nlogk)，因爲如果這是可能的[讓我們與複雜性O(g(n))其中g(n)是漸近弱且說nlogn] - 那麼我們就可以產生以下排序algorith：

sort(array A): 
    split A into n arrays, each of size 1, B1,...,Bn 
    A <- special_merge(B1,...Bn) 
    return A

很容易看出這個算法的複雜性爲O(g(n) + n) = O(g(n))，並且我們得到了一個折點，因爲我們得到的排序好於O(nlogn)--這對於基於區間的算法是不可能的，因爲這個問題是Omega(nlogn)

2012-03-30 09:52:28 amit

回答