整型数组合并

描述
题目标题：

将两个整型数组按照升序合并，并且过滤掉重复数组元素。
输出时相邻两数之间没有空格。
请注意本题有多组样例。

输入描述：
输入说明，按下列顺序输入：
1 输入第一个数组的个数
2 输入第一个数组的数值
3 输入第二个数组的个数
4 输入第二个数组的数值

输出描述：
输出合并之后的数组

示例1
输入：
3
1 2 5
4
-1 0 3 2

输出：
-101235

具体做法：

直接将输入的第二个数组接到第一个数组后面，后续对合并后的数组使用sort函数排序，然后遍历输出合并后的数组，对于与后面一个元素重复的情况我们不输出即可。

#include
#include
#include
using namespace std;

int main(){
    int n,m;
    while(cin>>n){
        vector vec1(n);
        for(int i=0;i>vec1[i];
        }
        cin>>m;
        vector vec2(vec1);
        for(int i=0;i>tmp;
            vec2.push_back(tmp);
        }
        sort(vec2.begin(), vec2.end());
        
        vec2.erase(unique(vec2.begin(), vec2.end()),vec2.end());
        for(int i=0;i 
复杂度分析： 
时间复杂度：
 O(nlog2n)，其中n为合并后两个数组的长度，sort函数使用了快排的原理，其他都是一次遍历
 空间复杂度：
 O(n)，使用了长度为n的空间来接受两个数组合并后的数组
 
方法二：集合 
具体做法：
 
采用set的自动排序和去重功能，将输入的数组每个元素插入集合中，最后遍历结合输出每个元素即是升序且去重的结果。
 
#include
#include
using namespace std;

int main(){
    int n, m;
    while(cin >> n){
        set s; //集合储存两个数组
        int temp;
        for(int i = 0; i < n; i++){ //输入第一个数组
            cin >> temp;
            s.insert(temp);
        }
        cin >> m;
        for(int i = 0; i < m; i++){ //输入第二个数组
            cin >> temp;
            s.insert(temp);
        }
        for(auto iter = s.begin(); iter != s.end(); iter++) //遍历集合
            cout << *iter; //输出每个元素
        cout << endl;
    }
    return 0;
}

 
复杂度分析： 
时间复杂度：
 O(nlog2n)其中n为合并后两个数组的长度，set借助了红黑树的排序功能，每次插入都是O(log2n)，一共n次插入
 空间复杂度：
 O(n)，最坏情况下所有元素都不同，集合大小为n
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658346.html