题意

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

方法

合并，排序，去重

  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⋅log(n))O(n\cdot log(n))，其余部分都是O(n)O(n)，所以总时间复杂度为O(n⋅log(n))O(n\cdot log(n))

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

分别排序，去重输出

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

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

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

i0(第一个数组的下标) i1(第二个数组的下标) 上次输出 本次输出
0 0 0x3f3f3f3f3f(超过int的值) 初始化无输出
0 0+1=1 -1 -1 (因为第二个数组的更小，所以输出并下标加1)
0 1+1=2 0 0(同理)
0+1=1 2 1 1
1+1=2 2 2 2(两边都是2，输出哪个都一样，这时输出第一个数组的
2 2+1=3 2 无，虽然2是最小的，但是和上次输出相等，去重
2 3+1=4 3 3
2+1=3 4 5 5(第二个数组已输出所有，所以接着输出剩余的第一个数组即可

代码

#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⋅log(n))O(n\cdot log(n))

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