思路:最直接的思路就是所有数据放到一个数组后再排序输出即可
#include<bits/stdc++.h>
#define maxn 10010
using namespace std;
int a[maxn];
int b[maxn];
int main(){
int n,m;
while(cin>>n){
for(int i=0;i<n;i++) cin>>a[i];
cin>>m;
for(int i=n;i<n+m;i++) cin>>a[i];
sort(a,a+n+m);
for(int i=0;i<n+m;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
那么我们还可以想到第二种思路就是跟归并排序差不多,两个数组,然后设立两个变量模拟指针,然后进行比较。
具体如下: 1.假设有数组A和数组B,然后数组A里面有n个元素,数组B里面有m和元素。 2.我们用一个nn表示数组A的指针,mm表示数组B的指针。 3.随后我们从两个数组头开始进行比较,如果数组A的元素小,就输出(记得打印空格),然后nn移动到后一格(即++),跟mm(此时还是数组B的第一个元素)指向的数进行比较。每次比较保证谁小谁输出谁移动指针即可,相等随意输出。 4.一个指针到头了(即nn >= n 或者 mm >= m)把另一个没到头的数组的元素全部输出即可。
#include<bits/stdc++.h>
#define maxn 10010
using namespace std;
int a[maxn];
int b[maxn];
int c[maxn];
int main(){
int n;
int m;
while(cin>>n){
for(int i=0;i<n;i++) cin>>a[i];
cin>>m;
for(int i=0;i<m;i++) cin>>b[i];
int nn = 0;
int mm = 0;
for(int i=0;;i++){
if(nn >= n || mm >= m) break;
if(a[nn] < b[mm]){
//cout<<"a<b:nn="<<nn<<" ";
cout<<a[nn]<<" ";
nn++;
//cout<<endl;
}
else{
//cout<<"a>=b:mm=="<<mm<<" ";
cout<<b[mm]<<" ";
mm++;
// cout<<endl;
}
}
if(nn != n)
for(int i=nn;i<n;i++) cout<<a[i]<<" ";
if(mm != m)
for(int i=mm;i<m;i++) cout<<b[i]<<" ";
cout<<endl;
}
return 0;
}
那么我们除了直接做法,我在学习数据结构,所以这个题目我们用有序线性表的合并来做。这才是重点啊 如下参考不知名大佬的code,orz
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
};
typedef Node* LinkList;
int n;
LinkList Create() {
LinkList L,pre,p;
L = new Node;
L->next = NULL;
pre = L;
for(int i = 0; i < n; ++i) {
p = new Node;
cin >> p->data;
p->next = NULL;
pre->next = p, pre = p;
}
return L;
}
LinkList Union(LinkList A, LinkList B) {
LinkList L,pre,p;
L = new Node;
L->next = NULL;
pre = L;
A = A->next, B = B->next;
while(A && B) {
p = new Node;
p->next = NULL;
if(A->data <= B->data) {
p->data = A->data;
A = A->next;
}
else if(A->data > B->data) {
p->data = B->data;
B = B->next;
}
pre->next = p, pre = p;
}
while(A) {
p = new Node;
p->data = A->data, p->next = NULL;
pre->next = p, pre = p;
A = A->next;
}
while(B) {
p = new Node;
p->data = B->data, p->next = NULL;
pre->next = p, pre = p;
B = B->next;
}
return L;
}
void Print(LinkList L) {
L = L->next;
int flag = 1;
while(L) {
if(flag) flag = 0, cout << L->data;
else cout << ' ' << L->data;
L = L->next;
}
cout << endl;
}
int main() {
while(cin >> n) {
LinkList A = Create();
cin >> n;
LinkList B = Create();
LinkList C = Union(A, B);
Print(C);
}
return 0;
}