wait 发表于 2015-12-28 22:49:50

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

       算法思路:取三个数组中的第一个元素,构建一个小顶堆,每次取堆顶元素,然后把最小元素对应的数组中的下一个元素添加到堆中,并调整为小顶堆,然后继续取堆顶元素,依次类推即可把三个有序数组合并为一个有序数组。这里采用类库提供的优先队列来作为小顶堆,实现代码如下:#include <iostream>
#include <queue>
#include<vector>
using namespace std;

struct Node
{
    int* arr;
    int len;
    int index;

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

Node* mergeArrays(Node* arrays, int len)
{
    if(arrays==NULL |len==0)
      return NULL;
    priority_queue<Node> queue;    //小根堆
    int count=0;
    //计算合并成一个有序数组的元素个数
    for(int i=0;i<len;i++)
    {
      queue.push(arrays);
      count+=arrays.len;
    }
    int* result = new int;
    int resultIndex=0;
   
    while(!queue.empty())
{
    //取出堆顶元素(最小值)
      Node node = queue.top();
      queue.pop();
      result=node.arr;
      //把最小值对应的数组中下一个元素加到队列(小顶堆)中
      if(node.index<node.len-1)
      {
            Node n(node.arr,node.len,node.index+1);
            queue.push(n);
      }
    }
    Node* n=new Node(result,count,0);
    return n;
}
int main()
{
    int arr1[] = { 1, 5, 9 };
    int arr2[] = { 2, 6, 10 };
    int arr3[] = { -1, 3, 7, 12 };
    Node n1(arr1,3,0);
    Node n2(arr2,3,0);
    Node n3(arr3,4,0);
    Node arrays[]={n1,n2,n3};
    Node* result=mergeArrays(arrays,3);
    for(int i=0;i<result->len;i++)
    {
      cout<<result->arr<<" ";
    }
    delete[] result->arr;
    delete result;
    return 0;
}


页: [1]
查看完整版本: 如何把三个有序数组合并为一个有序数组