有关交集问题

码拜

9年 ago

题目要求：题目描述
有两个相等长度的正整数序列A和B，都是有序的(递增排序)，同时一个序列中没有重复元素，现在需要求这两个序列的交――序列C，同时打印输出。
输入
每个测试用例一共有2*n+1行，第一行输入为数列的长度n，然后下面2~n+1行，依次输入序列A中的数。n+2~2*n+1行，依次输入序列B中的数。
其中 1 <= n <= 50000 , 序列中每个数大小不会超过1000000。当程序输入n为0时表示结束。
输出
每个测试用例输出一行，先输出序列C的长度，然后依次输出C中的整数，两个数之间间隔一个空格。注意行末不要出现空格。C中的整数递增排序。
本人的代码：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void display(int [],int);
int main()
{
int a[50010];
int b[50010];
int collection[50010];
int i,j,n,label=0;
while(scanf(“%d”,&n)!=EOF&&n!=0)
{
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
for(j=0;j<n;j++)
scanf(“%d”,&b[j]);
for(i = 0; i < n;i++)
{
for(j = 0;j < n;j++)
if(a[n-1]>=b[0])
{
if(a[i]==b[j])
{
collection[label]=a[i];
label++;
}
}
}
display(collection,label);
}

return 0;
}
void display(int num[],int count)
{
int i;
printf(“%d”,count);
for(i=0;i<count;i++)
{
printf(” %d”,num[i]);
}
printf(“\n”);
}
本人代码的问题在于：时间超限，有一种解决方法：先输入数组a并标记元素，然后再输入数组b比较，输出交集元素，问一下这种方法用代码怎么表示？

解决方案

引用:

Quote: 引用:

正好休息.来一个.

int main()
{
    int a[50010];
    int b[50010];
    int collection[50010];
    int i,j,n,label=0, aIndex = 0, bIndex = 0, cIndex = 0;
while(scanf("%d",&n)!=EOF&&n!=0)
{
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(j=0;j<n;j++)
        scanf("%d",&b[j]);
    aIndex = 0;
    bIndex = 0;
    cIndex = 0;
    while ( (aIndex < n) && (bIndex < n) )
    {
        if ( a[aIndex] == b[bIndex] )
        {
            collection[cIndex++] = a[aIndex];
            aIndex++;
            bIndex++;
        }
        else if ( a[aIndex] > b[bIndex] )
        {
            bIndex++;
        }
        else
        {
            aIndex++;
        }
    }
    display(collection,cIndex);
}
    return 0;
}

在占用内存空间较大的局部数组声明的前面加static将其从堆栈数据段挪到全局数据段即可避开因局部数组大小超过默认堆栈大小1MB造成程序不能正常运行的问题。

在他原来的基础上改的, 原来的能运行,现在的就能运行.
不要老找这些不痛不痒的毛病. 有本事就表明本人的观点.老是复制粘贴,真是够烦,看见你的回复就烦.