请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

猿媛之家

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 6906|回复: 0

如何把三个有序数组合并为一个有序数组

[复制链接]

44

主题

48

帖子

198

积分

注册会员

Rank: 2

积分
198
发表于 2015-12-28 22:49:50 | 显示全部楼层 |阅读模式
       算法思路:取三个数组中的第一个元素,构建一个小顶堆,每次取堆顶元素,然后把最小元素对应的数组中的下一个元素添加到堆中,并调整为小顶堆,然后继续取堆顶元素,依次类推即可把三个有序数组合并为一个有序数组。这里采用类库提供的优先队列来作为小顶堆,实现代码如下:
  1. #include <iostream>
  2. #include <queue>
  3. #include<vector>
  4. using namespace std;

  5. struct Node
  6. {
  7.     int* arr;
  8.     int len;
  9.     int index;

  10.     Node(int* arr, int len, int index)
  11.     {
  12.         this->arr=arr;
  13.         this->len=len;
  14.         this->index=index;
  15.     }
  16.     //自定义排序函数,从而使优先队列可以被作为小顶堆使用
  17.     friend bool operator <(Node n1, Node n2)  {  return n1.arr[n1.index]>n2.arr[n2.index]; }
  18. };

  19. Node* mergeArrays(Node* arrays, int len)
  20. {
  21.     if(arrays==NULL |len==0)
  22.         return NULL;
  23.     priority_queue<Node> queue;    //小根堆
  24.     int count=0;
  25.     //计算合并成一个有序数组的元素个数
  26.     for(int i=0;i<len;i++)
  27.     {
  28.         queue.push(arrays[i]);
  29.         count+=arrays[i].len;
  30.     }
  31.     int* result = new int[count];
  32.     int resultIndex=0;
  33.    
  34.     while(!queue.empty())
  35. {
  36.     //取出堆顶元素(最小值)
  37.         Node node = queue.top();
  38.         queue.pop();
  39.         result[resultIndex++]=node.arr[node.index];
  40.         //把最小值对应的数组中下一个元素加到队列(小顶堆)中
  41.         if(node.index<node.len-1)
  42.         {
  43.             Node n(node.arr,node.len,node.index+1);
  44.             queue.push(n);
  45.         }
  46.     }
  47.     Node* n=new Node(result,count,0);
  48.     return n;
  49. }
  50. int main()
  51. {
  52.     int arr1[] = { 1, 5, 9 };
  53.     int arr2[] = { 2, 6, 10 };
  54.     int arr3[] = { -1, 3, 7, 12 };
  55.     Node n1(arr1,3,0);
  56.     Node n2(arr2,3,0);
  57.     Node n3(arr3,4,0);
  58.     Node arrays[]={n1,n2,n3};
  59.     Node* result=mergeArrays(arrays,3);
  60.     for(int i=0;i<result->len;i++)
  61.     {
  62.         cout<<result->arr[i]<<" ";
  63.     }
  64.     delete[] result->arr;
  65.     delete result;
  66.     return 0;
  67. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|猿媛之家    

GMT+8, 2021-10-25 08:39 , Processed in 0.187352 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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