题目

假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素即为集合中的成员。编程实现集合A和集合B的并运算。

输入

第一行为集合A的数据元素个数n 第二行输入n个集合A的数据元素第三行为集合B的数据元素的个数；第四行输入m个集合B的数据元素。

输出

第一行为A和B的并集.

样例输入

8
0 5 6 3 8 7 9 10
7
1 3 4 7 8 9 5

样例输出

0 5 6 3 8 7 9 10 1 4

思路

方法1（暴力出奇迹）：

由于集合是没有重复元素的，所以同一个数据只会插入一次。

合并时，每一次插入新元素都遍历判断一次，如果有相同，那就跳过，判断下一个元素。如果不同，那就插入。

//合并顺序表
void SeqlistMerge(Seqlist* &La,Seqlist* &Lb) {for(int i=0;i<(Lb->len);i++) {int flag=1;//建立是否插入的判断旗帜for(int j=0;j<(La->len);j++) {if(Lb->data[i]==La->data[j]) {flag=0;//有相同元素，那不再插入。break;}}if(flag) La->data[La->len++]=Lb->data[i];}
}

方法2（桶，记忆化）：方法一，一看时间复杂度就是O(n?），为了减少时间复杂度，于是不妨先开个桶，先遍历顺序表a，让所有数对应的桶赋值为1(bucket[La->data[i]]=1)。然后插入顺序表b时判断，若为0则插入，然后桶赋值为1。下一次就直接跳过。这样就把时间复杂度省到了O(n)。

//合并集合
void SeqlistMerge(Seqlist* &La,Seqlist* &Lb) {int bucket[100005]={0};//建立桶for(int i=0;i<La->len;i++) {bucket[La->data[i]]=1;}for(int i=0;i<Lb->len;i++) {if(bucket[Lb->data[i]]==0) {La->data[La->len++]=Lb->data[i];bucket[Lb->data[i]]=1;}}
}

代码

顺序表模板查看

暴力

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义顺序表
typedef struct {int data[10005];int len;
}Seqlist;
// 初始化顺序表
void SeqlistInit(Seqlist* &L) {L=(Seqlist*)malloc(sizeof(Seqlist));L->len=0;
}
//创建顺序表，输入数据
void SeqlistCreate(Seqlist* &L) {int n,x;cin>>n;while(n--) {cin>>x;L->data[L->len++]=x;}
}
//合并顺序表
void SeqlistMerge(Seqlist* &La,Seqlist* &Lb) {for(int i=0;i<(Lb->len);i++) {int flag=1;//建立是否插入的判断旗帜for(int j=0;j<(La->len);j++) {if(Lb->data[i]==La->data[j]) {flag=0;//有相同元素，那不再插入。break;}}if(flag) La->data[La->len++]=Lb->data[i];}
}
//打印顺序表，输出数据
void SeqlistPrint(Seqlist* &L) {for(int i=0;i<(L->len)-1;i++) {cout<<(L->data[i])<<" ";}cout<<(L->data[L->len-1])<<endl;
}
int main() {Seqlist *La,*Lb;SeqlistInit(La);SeqlistCreate(La);SeqlistInit(Lb);SeqlistCreate(Lb);SeqlistMerge(La,Lb);SeqlistPrint(La);return 0;
}

记忆化

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义顺序表
typedef struct {int data[10005];int len;
}Seqlist;
// 初始化顺序表
void SeqlistInit(Seqlist* &L) {L=(Seqlist*)malloc(sizeof(Seqlist));L->len=0;
}
//创建顺序表，输入数据
void SeqlistCreate(Seqlist* &L) {int n,x;cin>>n;while(n--) {cin>>x;L->data[L->len++]=x;}
}
//合并集合
void SeqlistMerge(Seqlist* &La,Seqlist* &Lb) {int bucket[100005]={0};for(int i=0;i<La->len;i++) {bucket[La->data[i]]=1;}for(int i=0;i<Lb->len;i++) {if(bucket[Lb->data[i]]==0) {La->data[La->len++]=Lb->data[i];bucket[Lb->data[i]]=1;}}
}
//打印顺序表，输出数据
void SeqlistPrint(Seqlist* &L) {for(int i=0;i<L->len-1;i++) {cout<<L->data[i]<<" ";}cout<<L->data[L->len-1]<<endl;
}
int main() {Seqlist *La,*Lb;SeqlistInit(La);SeqlistCreate(La);SeqlistInit(Lb);SeqlistCreate(Lb);SeqlistMerge(La,Lb);SeqlistPrint(La);return 0;
}

STL

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>a,b;
int bucket[100005];
int main() {int m,n,x;cin>>m;while(cin>>x,bucket[x]=1,a.push_back(x),--m);cin>>n;while(cin>>x,bucket[x]=1,b.push_back(x),--n);vector<int>::iterator it;for(it=b.begin();it!=b.end();it++) a.push_back(*it);for(it=a.begin();it!=a.end();it++) {if(bucket[*it]) {cout<<*it<<" ";bucket[*it]=0;}}system("pause");return 0;
}

SWUST OJ#1037 集合的并运算

题目

思路

代码

暴力

记忆化

STL