题意

给两个数组，合并，排序，去重

方法

合并，排序，去重

1. 首先直接把两个数组读入到同一个数组中
2. 对这个数组排序
3. 对这个数组去重

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string line;
    int n;
    while (~scanf("%d",&n)){
        vector<int> arr;
        int v;
        for(int i = 0;i<n;i++){
            scanf("%d",&v);
            arr.push_back(v); // 读入到同一个数组中
        }
        scanf("%d",&n);
        for(int i = 0;i<n;i++){
            scanf("%d",&v);
            arr.push_back(v); // 读入到同一个数组中
        }
        sort(arr.begin(),arr.end()); // 排序
        int n = unique(arr.begin(), arr.end()) - arr.begin(); // 去重
        for(int i = 0;i < n;i++){
            printf("%d",arr[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 除了排序的部分是$O(n\cdot log(n))O(n\backslash cdot\; log(n))$，其余部分都是$O(n)O(n)$，所以总时间复杂度为$O(n\cdot log(n))O(n\backslash cdot\; log(n))$

空间复杂度: 主要消耗是记录数组，所以空间复杂度为$O(n)O(n)$

分别排序，去重输出

以题目样例1 2 5和-1 0 3 2两个数组为例子

首先， 对它们分别排序1 2 5,-1 0 2 3

然后采用双指针和一个上次输出，来完成输出与去重

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string line;
    int n;
    while (~scanf("%d",&n)){
        vector<int> arr0;
        int v;
        for(int i = 0;i<n;i++){
            scanf("%d",&v);
            arr0.push_back(v); // 数组1
        }
        vector<int> arr1;
        scanf("%d",&n);
        for(int i = 0;i<n;i++){
            scanf("%d",&v);
            arr1.push_back(v); // 数组2
        }
        sort(arr0.begin(),arr0.end()); // 分别排序
        sort(arr1.begin(),arr1.end());
        int i0 = 0;
        int i1 = 0;
        long long lastv = 0x3f3f3f3f3f; // 超过int 上一次输出的值
        while(i0 < arr0.size() || i1 < arr1.size()){
            if(i1 == arr1.size() || (i0 < arr0.size() && arr0[i0] <= arr1[i1])){ // 这次输出arr0
                if(arr0[i0] != lastv){ // 判断重复
                    printf("%d",arr0[i0]);
                    lastv = arr0[i0];
                }
                i0++;
            }else{ // 输出arr1
                if(arr1[i1] != lastv){ // 判断重复
                    printf("%d",arr1[i1]);
                    lastv = arr1[i1];
                }
                i1++;
            }
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 除了排序，其余内容都是线性复杂度，所以总时间复杂度为$O(n\cdot log(n))O(n\backslash cdot\; log(n))$

空间复杂度: 主要消耗是记录数组，所以空间复杂度为$O(n)O(n)$