📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

google(1) 合并k个排序数组

 
🔗
benny 2011-4-18 03:25:15 | 只看该作者
全局:
本帖最后由 benny 于 2011-4-18 04:51 编辑

我觉得可以用size是N的最小堆吧
这样就是O(M*log N), M是所有元素的个数

第一次把N个数列的第一个元素放进去,排成最小堆。

把堆顶的元素拿出去,把这个元素对应的数列的下一个数放到堆里,再排成最小堆
以此循环M次,每次排序都是lgN的复杂度

Therefore, O(M*log N)

按照W大的意思,我写的答案是白色的……

评分

参与人数 1大米 +50 萝卜 +32 收起 理由
Warald + 50 + 32 benny同学是细心人!!

查看全部评分

回复

使用道具 举报

🔗
Imbalism 2011-4-18 11:54:21 | 只看该作者
全局:
本帖最后由 Imbalism 于 2011-4-18 20:39 编辑

赞楼上几位大哥勤学好问的精神,  我的代码,用priority queue实现的。新手上路,求喷
想不出来用归并排序的思想如何实现, 求指导
  1. //problem description: merge K sorted lists with total N elements
  2. //solution: put the front element of each list into a priority queue,
  3. //    till finish, pop the min value from the priority queue, and enqueue
  4. //    the next element in corresponding list, delete that element
  5. //time complexity:
  6. //         select min value in the queue with K elements: O(lgK)
  7. //         repeat O(n) times
  8. //         time complexity = O(n * lgK)
  9. //space complexity:
  10. //         output array = O(n)
  11. //         priority queue = O(k)
  12. //         space complexity = O(n + k) = O(n)
  13. #include <queue>
  14. #include <list>
  15. #include <vector>
  16. #include <iostream>
  17. using namespace std;

  18. //support compare function for priority heap
  19. struct Comparator
  20. {
  21.      bool operator()(const list<int>*a, const list<int>*b) const
  22.           {
  23.                if(b->size() == 0)
  24.                     return false;
  25.                return a->front() > b->front();
  26.           }
  27. };

  28. vector<int> nWayMerge(list<list<int> >& l)
  29. {
  30.      vector<int> output;
  31.      priority_queue<list<int>*, vector<list<int>* >, Comparator> q;
  32.      list<list<int> >::iterator iter;
  33.      //initialize the priority queue by
  34.      //putting each list
  35.      //into the queue     
  36.      for(iter = l.begin(); iter != l.end(); iter++)
  37.           q.push(&*iter);
  38.      
  39.      //once the min list goes empty,
  40.      //we know all elements has been dealed
  41.      while(q.top()->size() != 0)
  42.      {
  43.           //pop the min element in the queue
  44.           output.push_back(q.top()->front());
  45.           q.top()->pop_front();
  46.           list<int>* l = q.top();
  47.           q.pop();
  48.           q.push(l);
  49.      }
  50.      return output;
  51. }
  52. int main()
  53. {
  54.      //test cases with 3 sorted lists
  55.      list<list<int> > input;
  56.      list<int> l1 = {12, 15, 16, 18, 20};
  57.      list<int> l2 = {11, 13, 18, 20, 22};
  58.      list<int> l3 = {9, 14, 15, 20, 23};
  59.      input.push_back(l1);
  60.      input.push_back(l2);
  61.      input.push_back(l3);
  62.      vector<int> v = nWayMerge(input);
  63.      for(vector<int>::iterator iter = v.begin(); iter != v.end(); iter++)
  64.           cout << *iter << endl;
  65.      return 0;
  66. }
复制代码
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-18 12:52:45 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-4-18 12:53 编辑

我觉得可以用size是N的最小堆吧
这样就是O(M*log N), M是所有元素的个数

第一次把N个数列的第一个元素放 ...
benny 发表于 2011-4-18 03:25


不错哦,也是一种解法,但是如果题目给出的是合并n个链表的话,则排序的思想是最优的,实现容易,也不占用额外的存储空间
回复

使用道具 举报

🔗
liuzxiao 2011-4-18 14:14:17 | 只看该作者
全局:
归并排序的思想,把元素换成数组来考虑?
回复

使用道具 举报

🔗
danielgao 2011-4-19 03:47:34 | 只看该作者
全局:
maintain 1个size为N的最小堆,堆里面每个element是一个(val, index)的pair,val是数组a[index]的当前元素,每次把堆顶元素出堆,然后把堆顶元素的下一个元素进堆,如果N个数组总size是M,那么时间复杂度是MlogN
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表