题目链接

https://www.nowcoder.com/practice/c4f11ea2c886429faf91decfaf6a310b?tpId=37&&tqId=21303&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37%26type%3D37%26page%3D2

题目描述

将两个整型数组按照升序合并,并且过滤掉重复数组元素。 输出时相邻两数之间没有空格。

方法一:hash + 排序

先将两个数组合并,按升序进行排序后,因为相同的元素只能出现一次,故我们可以在遍历数组时对每个元素用map标记是否已经被遍历,若已经被遍历则不再输出,若还未被遍历则输出并且更改当前标记。

结合图示理解此思路: 以题面给出的样例为例:

数组一: 1 2 5

数组二: -1 0 3 2

合并升序排序得到新数组:-1 0 1 2 2 3 5 遍历过程: alt

参考代码:

#include <bits/stdc++.h>

using namespace std;
vector<int> arr;
int n, m;

int main() {
	while (cin >> n) {           //多组测试数据
		arr.clear();
        //输入与合并两个数组
		for (int i = 1; i <= n; i ++ ) {
			int x; cin >> x;
			arr.push_back(x);
		}
		cin >> m;
		for (int i = 1; i <= m; i ++ ) {
			int x; cin >> x;
			arr.push_back(x);
		}
        //对合并数组升序排序
		sort(arr.begin(), arr.end());
		map<int, int> st;
        vector<int> ans;
        //遍历并保存未标记元素
        for (int i = 0; i < arr.size(); i ++ ) {
            if (!st[arr[i]]) {
                st[arr[i]] = 1; //更新标记
                ans.push_back(arr[i]);
            }
        }
        for (int i = 0; i < ans.size(); i ++ ) cout << ans[i];
        cout << "\n";
	}
		
	return 0;
} 

时间复杂度: 遍历数组的复杂度为O(n), 排序数组复杂度为O(nlogn),故总复杂度为O(nlogn)

空间复杂度: 因为有多组测试数据,故为O(n)

方法二:直接使用stl函数

iterator unique(iterator it_1,iterator it_2) : 这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1,it_2)范围的元素进行去重(注:区间是前闭后开,即不包含it_2所指的元素),返回值是一个迭代器,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。 故我们可以将两个数组合并排序后通过unique去重得到的即为不出现重复的新数组。

参考代码:

#include <bits/stdc++.h>

using namespace std;
vector<int> arr;
int n, m;

int main() {
	while (cin >> n) {           //多组测试数据
		arr.clear();
        //输入与合并两个数组
		for (int i = 1; i <= n; i ++ ) {
			int x; cin >> x;
			arr.push_back(x);
		}
		cin >> m;
		for (int i = 1; i <= m; i ++ ) {
			int x; cin >> x;
			arr.push_back(x);
		}
        //对合并数组升序排序
		sort(arr.begin(), arr.end());
        //去重
		arr.erase(unique(arr.begin(), arr.end()), arr.end());
        for (auto i : arr) cout << i;
        cout << "\n";
	}
		
	return 0;
} 

时间复杂度:排序之后unique的时间复杂度为O(n), 排序复杂度为O(nlogn),故总复杂度为O(nlogn)

空间复杂度: O(n)