题目链接
题目描述
将两个整型数组按照升序合并，并且过滤掉重复数组元素。 输出时相邻两数之间没有空格。
方法一：hash + 排序
先将两个数组合并，按升序进行排序后，因为相同的元素只能出现一次，故我们可以在遍历数组时对每个元素用map标记是否已经被遍历，若已经被遍历则不再输出，若还未被遍历则输出并且更改当前标记。
结合图示理解此思路： 以题面给出的样例为例：
数组一： 1 2 5
数组二： -1 0 3 2
合并升序排序得到新数组：-1 0 1 2 2 3 5
遍历过程：
参考代码：
#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;
}
京公网安备 11010502036488号