以下是一些 Python 2 代码，用于合并。
import heapq
def addtoheap(h, i, it):
try:
heapq.heappush(h, (next(it), i))
except StopIteration:
pass
def mergek(*lists):
its = map(iter, lists)
h = []
for i, it in enumerate(its):
addtoheap(h, i, it)
while h:
v, i = heapq.heappop(h)
addtoheap(h, i, its[i])
yield v
for x in mergek([1, 3, 5], [2, 4, 6], [7, 8, 9], [10]):
print x
为什么时间复杂度是O(n log k)？因为对于每个被移除的值，都需要执行一次堆弹出和可能的堆插入操作（这两个操作的时间复杂度都是O(log k)）。由于我们要移除n个元素，所以总时间复杂度是O(n log k)。
i，你可以使用heappush(h, (next(it), it))。 - jfs与其仅将每个列表的第一个元素存储在优先队列中，不如将其包装在这样的结构中：
struct wrapper
{
int list_number;
int element;
}
这是我的使用C++ STL的代码
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#define ROWS 4
#define COLS 8
using namespace std;
struct node
{
int ele;
int arr_no;
int next_index;
};
void printVector(vector<int> v)
{
for(unsigned int i=0;i<v.size();i++)
cout<<v[i]<<" ";
}
// THIS IS THE BASIS ON WHICH THE ELEMENTS OF A PRIORITY QUEUE ARE SORTED AND
// KEPT IN THE QUEUE, HERE THE CRITERIA IS THAT THE NODE WITH SMALLER ELEMENT SHOULD
// COME ABOVE THE ONE WITH LARGER ELEMENT
class compare
{
public:
bool operator()(node& n1, node& n2)
{
if (n1.ele > n2.ele)
return true;
else
return false;
}
};
vector<int> mergeKArrays(vector< vector<int> > v)
{
int k = v.size(); // NUMBER OF LISTS
int n = v.at(0).size(); //SIZE OF EACH LIST
vector<int> result;
//result.resize( n*k );
priority_queue<node, vector<node>, compare> minHeap;
for (int i = 0; i < k; i++)
{
node temp;
temp.ele = v[i][0]; //STORE THE FIRST ELEMENT
temp.arr_no = i; //INDEX OF ARRAY
temp.next_index = 1; //INDEX OF NEXT ELEMENT TO BE STORED FROM ARRAY
minHeap.push(temp);
}
// NOW ONE BY ONE GET THE MINIMUM ELEMENT FROM MIN
// HEAP AND REPLACE IT WITH NEXT ELEMENT OF ITS ARRAY
for (int count = 0; count < n*k; count++)
{
// GET THE MINIMUM ELEMENT AND STORE IT IN OUTPUT
node min_ele_node = minHeap.top();
minHeap.pop();
result.push_back(min_ele_node.ele);
// FIND THE NEXT ELELEMENT THAT WILL REPLACE CURRENT
// ROOT OF HEAP. THE NEXT ELEMENT BELONGS TO SAME
// ARRAY AS THE CURRENT ROOT.
node new_node;
new_node.arr_no = min_ele_node.arr_no;
if (min_ele_node.next_index < n)
{
new_node.ele = v.at(min_ele_node.arr_no)[min_ele_node.next_index];
new_node.next_index = min_ele_node.next_index + 1;
}
// IF ROOT WAS THE LAST ELEMENT OF ITS ARRAY
else
{
new_node.ele = INT_MAX; //INT_MAX IS FOR INFINITE
}
// REPLACE ROOT WITH NEXT ELEMENT OF ARRAY
minHeap.push(new_node);
}
return result;
}
int main()
{
int arr[ROWS][COLS] =
{
{10, 20, 30, 40, 50, 60, 71, 86},
{15, 25, 35, 45, 60, 69, 77, 78},
{27, 29, 37, 48, 50, 65, 75, 78},
{32, 33, 39, 50, 80, 133, 139, 150},
};
vector< vector<int> > matrix ;
for( int i=0 ; i < ROWS; i++)
{
vector<int> vec;
for(int j=0; j < COLS; j++)
vec.push_back(arr[i][j]);
matrix.push_back(vec);
}
vector<int> result = mergeKArrays(matrix);
printVector(result);
return 0;
}
Paul Hankin的解决方案是正确的，但阅读起来有点困难，特别是你想在c++或java中实现。我的解决方案与Paul的类似。如果你用c++或java编写，可能需要一个额外的数据结构来存储元素的值、k-th数组中元素的索引和列表中数组的索引。
Element{
int value;
int idInArray,
int idInList
}
def mergeKArray(*lists):
# implemented by min heap
h = []
r = []
for k, arr in enumerate(lists):
heapq.heappush(h, (arr[0], 0, k))
while h:
# min is the minimum element
# i is the index of the min in the k-th array
# k is the index of array in the list
min, i, k = heapq.heappop(h)
r.append(min)
if i < len(lists[k]) - 1:
i += 1
heapq.heappush(h, (lists[k][i], i, k))
return r
因为我只需要维护一个包含k个元素的最小堆，所以弹出或插入堆的时间复杂度为O(log k)。我还需要扫描所有n个元素，每个元素插入和弹出堆的时间复杂度为2*log(k)。因此，总的时间复杂度为O(n*log k)。
1 当列表没有更多元素时，它被耗尽了。
2 你需要跟踪最小元素来自哪个列表
3 对于每个元素，将其放入大小为k的最小堆中，这需要logk的时间，因此您需要n次logk。
n个元素，并且每个元素都被插入/从k大小的堆中删除。算法中的所有其他工作都被这些步骤“吸收”了。 - rliu