7-1 两个有序链表序列的合并 (20分) --- 内存问题再叙

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

 

 

 

---

题解

 

这次又是取“并集”，可以与我的 https://blog.csdn.net/rAiNFalLzZ/article/details/107435297  一起看。

这次我吸取上次经验，开了两个数组，然后用的双指针移动法。但如果不把结果存在数组里，一旦代码比较复杂(这里指输出的情况众多)，就会很恶心。我没开c数组，是怕复杂度上去。

 

ac代码

#include<bits/stdc++.h>
using namespace std;

int a[10000000],top1=1;
int b[10000000],top2=1;

int main()
{
	while(cin>>a[top1])
	{
		if(a[top1]==-1)
		{
			top1--;
			break;
		}
		top1++;	
	}
	while(cin>>b[top2])
	{
		if(b[top2]==-1)
		{
			top2--;
			break;
		}
		top2++;	
	}
	
	if(top1==0&&top2==0)
	{
		cout<<"NULL\n";
		return 0;
	}
	
	int start=1;        //操蛋的开始，这个start要我命
	int p1=1,p2=1;
	while(p1<=top1&&p2<=top2)
	{
		if(a[p1]>b[p2])
		{
			if(start==1)
			{
				cout<<b[p2];
				start=0;
			}
			else
				cout<<" "<<b[p2];
			p2++;
		}
		else if(a[p1]<b[p2])
		{
			if(start==1)
			{
				cout<<a[p1];
				start=0;
			}
			else
				cout<<" "<<a[p1];
			p1++;
		}
		else
		{
			if(start==1)
			{
				cout<<a[p1]<<" "<<a[p1];
				start=0;
			}
			else
			{
				cout<<" "<<a[p1]<<" "<<a[p1];
			}
			p1++;
			p2++;
		}
	}
	if(p1>top1&&p2<=top2)
	{
		for(int i=p2;i<=top2;i++)
		{
			if(start==1)
			{
				start=0;
				cout<<b[i];	
			}	
			else		cout<<" "<<b[i];
		}	
	}
	else if(p1<=top1&&p2>top2)
	{
		for(int i=p1;i<=top1;i++)
		{
			if(start==1)
			{
				cout<<a[i];	
				start=0;
			}	
			else		cout<<" "<<a[i];
		}	
	}

	return 0;
}

 

不知道有没有好的办法可以在保证原有思路下不会出现这样重复的东西。

 

接下来说收获。

 

收获1. 内存问题的新理解

如以前记下的。

局部变量的存储空间(栈) 为 1M 。

全局变量的存储(静态区) 为 2G。

动态分配的存储为 当前硬盘大小。

 

换算关系： 1 GB = 1024 MB = 1024*1024 KB

 

PTA的题目简介

时间也是一个参考，这里不说，这里主要说空间。

空间限制为 125 MB ，也就是说开的空间字节数在这个范围内就能够解决问题。

这也只是个参考，我发现我开到了230 MB也可以通过。

目前可以说，空间适当大一些没有问题。

 

但小了不行。

 

其实我比赛时，本题没有过。

我开了两个1000000，共占用8000000byte = 8M，符合题目的125M限制。

但没有过，我当时也没有往大了开。

现在突然看到最后一点的内存为11608KB = 11M(近似) ，倘若需要11 M，而我只开了8M ,结果可想而知。以前一直忽略这个内存，现在才发现这也是提示。

后来我改成了两个10000000数组，大约80M，就过了。

 

综上，数组题遇到点不过而思路检查没有问题时，就可以考虑是不是开的空间小了。

空间大一些没关系，但要小一些就是过不了。很多时候，死马当活马医地去扩大数组空间，也许就能过。

PTA测试点的内存也是一个提示，看看自己开的内存能不能装下测试点的内存。

 

 

 

收获2：并集新解法

直接把两个数组当成一个数组来读取。然后用sort快排就行啦。

 

ac代码

#include<bits/stdc++.h>
using namespace std;

int a[30000000],top=0;

int main()
{
	int item;
	while(cin>>item)
	{
		if(item==-1)	break;
		else
			a[++top] = item;	
	}
	
	
	while(cin>>item)
	{
		if(item==-1)	break;
		else
			a[++top] = item;	
	}
	
	if(top==0)
	{
		cout<<"NULL";
		return 0;
	}
	
	sort(a+1,a+top+1);
	for(int i=1;i<=top;i++)
	{
		if(i==1)	cout<<a[i];
		else		cout<<" "<<a[i];
	}
	
	
	return 0;
}

 

本文地址：https://blog.csdn.net/rAiNFalLzZ/article/details/107596538