intersection of k sorted list
今天发现pop_heap的问题(后来发现似乎是MSVC里那个蛋疼的pop_heap的问题)，于是再写了一遍intersection of k sorted list.
而且发现了之前那个微博童鞋代码的问题，没有考虑list里面有NULL的情况。
不过我的代码似乎稍微繁琐一些，不是那么简洁。
里面更换heap顶 然后调整还是用了pop_heap push_heap来做的，因为直接make_heap毕竟是线性时间复杂度。
由于作者的数据是倒序的，倒序是要维护min 和maxheap的，所以需要用头插法简历list，而且如果用STL的list也不好弄。
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>
//#include <cstddef>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x):val(x),next(nullptr)
{
}
};
bool comp(const ListNode* p1, const ListNode* p2)
{
return p1->val>p2->val;//greater than, min heap// less than, default, is max heap
}
vector<int> intersection(vector<ListNode*> v)
//process ascending sort, using max, minheap, check whether min of heap(top) is max, if is, then whole is equal,
//process descending sort, using min, maxheap, check whether max of heap(top) is min, if is, then whole is equal;
{
vector<int> intervec;
for(int i=0;i<v.size();i++)
if(v[i]==nullptr)
return intervec;
make_heap(v.begin(),v.end(),comp);//min heap of node *
int maxv=0xFFFFFFFF;
for(int i=0;i<v.size();i++)
if(maxv<v[i]->val)
maxv=v[i]->val;
while(true)
{
if(v.front()->val==maxv)
{
intervec.push_back(maxv);
//bool hasnull=false;
int i;
for(i=0;i<v.size();i++)
{
if(v[i]->next==NULL)
{
//hasnull=true;
break;
}
else
v[i]=v[i]->next;
}
if(i<v.size())
break;
}
else
{
if(v.front()->next==nullptr)
{
break;
}
v.front()=v.front()->next;
maxv=max(maxv,v.front()->val);
//swap(v.front(),v.back());
//v.resize(v.size()-1);
//make_heap(v.begin(),v.end(),comp);
pop_heap(v.begin(),v.end(),comp);
push_heap(v.begin(),v.end(),comp);
/*
*/
}
}
return intervec;
}
ListNode* InsertHead(int a[], int n)// list::push_front()
{
if(n==0) return nullptr;
ListNode* head=new ListNode(a[0]);
//head->val=a[0];
for(int i=1;i<n;i++)
{
ListNode* p =head;
head=new ListNode(a[i]);
head->next=p;
}
return head;
}
int main()
{
int a[]={111,99,19,18,10,9,8,6,5,4,3,2,1,-1,-2,
111,99,19,11,10,9,7,5,4,3,2,1,0,-1,-3,
99,21,20,19,18,17,16,10,8,6,4,2,1,0,-1,
112,111,99,97,96,95,90,30,29,28,27,23,20,-1,-2,
110,110,99, 87,86,85, 80,80,79, 78,77,73, 71,71,62,
1110,1110,188,187,186,185,180,180,179,178,177,111,99,1,-1};
int n=sizeof(a)/sizeof(int);
int pern=15;
/*
list<int> sortedlist[n/pern];
for(int i=0;i<n;i++)
{
sortedlist[i/pern].push_front(a[i]);
}
*/
vector<ListNode* > v;
for(int i=0;i<n/pern;i++)
{
v.push_back(InsertHead(a+pern*i,pern));
}
vector<int> intervec=intersection(v);
for(int i=0;i<intervec.size();i++)
printf("%d ",intervec[i]);
return 0;
}