中级农民
- 积分
- 133
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-3-5
- 最后登录
- 1970-1-1
|
本帖最后由 Imbalism 于 2011-4-18 20:39 编辑
赞楼上几位大哥勤学好问的精神, 我的代码,用priority queue实现的。新手上路,求喷
想不出来用归并排序的思想如何实现, 求指导
- //problem description: merge K sorted lists with total N elements
- //solution: put the front element of each list into a priority queue,
- // till finish, pop the min value from the priority queue, and enqueue
- // the next element in corresponding list, delete that element
- //time complexity:
- // select min value in the queue with K elements: O(lgK)
- // repeat O(n) times
- // time complexity = O(n * lgK)
- //space complexity:
- // output array = O(n)
- // priority queue = O(k)
- // space complexity = O(n + k) = O(n)
- #include <queue>
- #include <list>
- #include <vector>
- #include <iostream>
- using namespace std;
- //support compare function for priority heap
- struct Comparator
- {
- bool operator()(const list<int>*a, const list<int>*b) const
- {
- if(b->size() == 0)
- return false;
- return a->front() > b->front();
- }
- };
- vector<int> nWayMerge(list<list<int> >& l)
- {
- vector<int> output;
- priority_queue<list<int>*, vector<list<int>* >, Comparator> q;
- list<list<int> >::iterator iter;
- //initialize the priority queue by
- //putting each list
- //into the queue
- for(iter = l.begin(); iter != l.end(); iter++)
- q.push(&*iter);
-
- //once the min list goes empty,
- //we know all elements has been dealed
- while(q.top()->size() != 0)
- {
- //pop the min element in the queue
- output.push_back(q.top()->front());
- q.top()->pop_front();
- list<int>* l = q.top();
- q.pop();
- q.push(l);
- }
- return output;
- }
- int main()
- {
- //test cases with 3 sorted lists
- list<list<int> > input;
- list<int> l1 = {12, 15, 16, 18, 20};
- list<int> l2 = {11, 13, 18, 20, 22};
- list<int> l3 = {9, 14, 15, 20, 23};
- input.push_back(l1);
- input.push_back(l2);
- input.push_back(l3);
- vector<int> v = nWayMerge(input);
- for(vector<int>::iterator iter = v.begin(); iter != v.end(); iter++)
- cout << *iter << endl;
- return 0;
- }
复制代码 |
|