Merge K sortedlist
这道题目是归并K个链表，其实也就是二路归并的扩展，但是出了很多coding的状况，导致花了很多时间，
最严重的错误，因为自己有强迫症，min或max的时候能不用宏定义一个MAXNUM就尽量不用，避免局限性，于是min先赋第一个值，结果没考虑到这个min的遍历还要筛选非空的结点，
于是这里挂了，如果还是用原来的话，还要先找一个非空的结点，非常麻烦，所以还是用MAXNUM，其实也可以用前面判断函数返回的一个非空值作为min初始值的当前比较的最小值链表后移写成了指针后移，pointer[mini]=pointer[mini]->next，主要是这种写法太深入自己了，以至于没有因地制宜，显然是修改lists这个vector对应的值，不过发现其实这个写法就是
这样写的，原来当时的错误只是没注意mini写成了min了。
3.再由就是思考特殊输入用例的时候，一开始没想清楚，从k值0,1,2逐个讨论，后来发现即使K>=2也是需要特殊处理的，如果里面少于两个非空链表，因此特殊情况其实可以统一成是否K个lists里面
有少于2个非空链表，于是代码简洁多了。
但是这个朴素的算法TLE了，leetcode很多TLE其实是程序crashed，由于边界没处理好。但是这个应该是真的TLE了，因为输入很大。
class Solution {
public:
int MAXNUM=10000000;
bool HasAtleastTwoNonNUll(vector<ListNode* >lists, ListNode*& remainpointer)
{
int count=0;
for(int i=0;i<lists.size();i++)
{
if(lists[i]!=NULL)
count++,remainpointer=lists[i];
if(count>=2) return true;
}
return false;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
/*if(lists.size()==0) return NULL;
if(lists.size()==1) return lists[0];
if(lists.size()==2)
{
if(lists[0]==NULL)
return lists[1];
else
return lists[0];
}*/
bool first=true;
ListNode* head,*remainpointer=NULL, *currenttail;
vector<ListNode*> pointer=lists;
if(HasAtleastTwoNonNUll(lists, remainpointer)==false)
{
return remainpointer;
}
while(HasAtleastTwoNonNUll(pointer, remainpointer))
{
int min=MAXNUM,mini;
for(int i=0;i<pointer.size();i++)
{
if(pointer[i]!=NULL && pointer[i]->val<min)
min=pointer[i]->val, mini=i;
}
if(first==true)
head=pointer[mini],currenttail=head,first=false, pointer[mini]=pointer[mini]->next;
else
currenttail->next=pointer[mini],currenttail=currenttail->next,pointer[mini]=pointer[mini]->next;
}
currenttail->next=remainpointer;
return head;
}
};
后来想想主要是自己的算法太朴素了，尤其是找最值的那部分，建个堆，然后里面用堆优越的查找性能来提高效率。
由于还要找到linklist的索引，因此需要一个pair，我之前总是会先考虑struct node，但是现在不会了，自从看了adhoc的代码，连三个元素他都用 make_pair两次。。。
DS讲的存单个元素到实际几乎没法用，但是思想很重要，导出其实都是
时间复杂度瞬间从O(MK) 降到O(MlogK), 当K较大的时候不得不说是一个巨大的性能提升
STL中堆的几个算法如下http://blog.csdn.net/morewindows/article/details/6967409：
make_heap(_First, _Last, _Comp) 建堆，默认最大堆，greater
在堆中添加数据
push_heap (_First, _Last)
要先在容器中加入数据，再调用push_heap ()
在堆中删除数据
pop_heap(_First, _Last)
要先调用pop_heap()再在容器中删除数据
堆排序
sort_heap(_First, _Last)
排序之后就不再是一个合法的heap了
make_heap里面是O(n)的建堆算法，pop_heap实现的是讲最后与第一个元素交换，然后filterdown O(logn)
push_heap实现的是尾插一个元素，然后filterdown O(logn)
然后单独处理一下head结点，以及最后只剩1个或0个指针非空的情况就可以了。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//#define MAXNUM 1000000
bool comp(const pair<int,int> p1,const pair<int,int> p2)
{
return p1.first>p2.first;
}
int HasAtleastTwoNonNUll(vector<ListNode* >lists, ListNode*& remainpointer)
{
int count=0;
for(int i=0;i<lists.size();i++)
{
if(lists[i]!=NULL)
count++,remainpointer=lists[i];
//if(count>=2) return count;
}
return count;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
/*if(lists.size()==0) return NULL;
if(lists.size()==1) return lists[0];
if(lists.size()==2)
{
if(lists[0]==NULL)
return lists[1];
else
return lists[0];
}*/
bool first=true;
ListNode* head,*remainpointer=NULL, *currenttail;
vector<ListNode*> pointer=lists;
int count;
if((count=HasAtleastTwoNonNUll(lists, remainpointer))<=1)
{
return remainpointer;
}
//int count=HasAtleastTwoNonNUll(pointer, remainpointer);
vector<pair<int,int> > alllistvalue;
for(int i=0;i<pointer.size();i++)
{
if(pointer[i]!=NULL)
{
pair<int,int> valueindex=make_pair(pointer[i]->val,i);
alllistvalue.push_back(valueindex);
}
}
make_heap(alllistvalue.begin(),alllistvalue.end(),comp);
while(1)
{
if(count<=1)
{
break;
//count=HasAtleastTwoNonNUll(pointer, remainpointer);
//if(count)
}
int mini;
/*
for(int i=0;i<pointer.size();i++)
{
if(pointer[i]!=NULL && pointer[i]->val<min)
min=pointer[i]->val, mini=i;
}
*/
mini=alllistvalue[0].second;
pop_heap(alllistvalue.begin(),alllistvalue.end(),comp);
alllistvalue.pop_back();
if(first==true)
{
head=pointer[mini],currenttail=head,first=false, pointer[mini]=pointer[mini]->next;
if(pointer[mini]==NULL)
{
count--;
}
else
{
//pop_heap(alllistvalue.begin(),alllistvalue.end(),comp);
//alllistvalue.pop_back();
pair<int,int> newminpair=make_pair(pointer[mini]->val,mini);
alllistvalue.push_back(newminpair);
push_heap(alllistvalue.begin(),alllistvalue.end(),comp);
}
}
else
{
currenttail->next=pointer[mini],currenttail=currenttail->next,pointer[mini]=pointer[mini]->next;
if(pointer[mini]==NULL)
{
//pop_heap(alllistvalue.begin(),alllistvalue.end(),comp);
//alllistvalue.pop_back();
count--;
}
else
{
//pop_heap(alllistvalue.begin(),alllistvalue.end(),comp);
//alllistvalue.pop_back();
pair<int,int> newminpair=make_pair(pointer[mini]->val,mini);
alllistvalue.push_back(newminpair);
push_heap(alllistvalue.begin(),alllistvalue.end(),comp);
}
}
}
if(alllistvalue.size()==0)
;
else if(alllistvalue.size()==1)
{
currenttail->next=pointer[alllistvalue[0].second];
}
/*
remainpointer=NULL;
HasAtleastTwoNonNUll(pointer, remainpointer);
currenttail->next=remainpointer;
*/
return head;
}
ListNode* create(int *a, int n)
{
if(n==0) return NULL;
ListNode*head=new ListNode(a[0]),*tail=head;
int i=1;
while(i<n)
{
ListNode* tmp=new ListNode(a[i]);
tail->next=tmp;
tail=tail->next;
i++;
}
tail->next=NULL;
return head;
}
void Show(ListNode* head)
{
while(head!=NULL)
cout<<head->val<<" ",head=head->next;
cout<<endl;
}
int main()
{
int a1[]={-1,1},a2[]={-3,1,4},a3[]={-2,-1,0,2};
ListNode* list1=create(a1,sizeof(a1)/sizeof(int));
ListNode* list2=create(a2,sizeof(a2)/sizeof(int));
//ListNode* list3=NULL;
ListNode* list3=create(a3,sizeof(a3)/sizeof(int));
//ListNode* list2=new ListNode(1);
vector<ListNode*> lists;
lists.push_back(list1);
lists.push_back(list2);
lists.push_back(list3);
//lists.push_back(list4);
ListNode* head=mergeKLists(lists);
Show(head);
return 0;
}