使用O合併數據流（1）RAM

Question

如何使用O（1）RAM合併k個排序的數據流？我應該如何定義數據流對象及其相關的功能/操作？

我的解決方案：我想使用數組列表作爲數據流對象。我計劃尋找k數組列表的第0個索引的最小值。最小值應該從該數組列表中刪除，並且應該將其放在輸出數組列表中。這個過程應該重複，直到所有的k數組列表都變爲null。但我想這將花費O（k *每個數組列表的長度）。任何想法如何在O（1）中做到這一點？

Answer 1

製作O（1）ram算法非常依賴於您的基礎數據結構和選擇的語言。假設你知道如何帶O操作你的數據結構（1）RAM看到這一點：

http://en.wikipedia.org/wiki/Merge_sort

的合併功能需要O（1）內存。現在，您需要的只是一組數據流的索引，並將所有數據流合併到第一個數據流中，然後完成。