用c/c++完整写出代码设计算法以删除顺序表中重复的元素,并分析算法的时间性能
时间: 2023-07-15 08:09:58 浏览: 48
以下是使用C++编写的删除顺序表中重复元素的算法:
```cpp
template<typename T>
void deleteRepeat(vector<T>& v) {
int i = 0, j = 0;
int n = v.size();
unordered_set<T> s;
while (j < n) {
if (s.find(v[j]) == s.end()) {
s.insert(v[j]);
v[i++] = v[j];
}
j++;
}
v.resize(i);
}
```
该算法使用了一个`unordered_set`来保存已经出现过的元素,然后遍历整个数组,如果当前元素没有出现过,则将其加入`unordered_set`中,并将其放到数组的前面。由于使用了`unordered_set`,查找元素的时间复杂度为O(1)。因此,该算法的时间复杂度为O(n)。
以下是完整的测试代码:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
template<typename T>
void deleteRepeat(vector<T>& v) {
int i = 0, j = 0;
int n = v.size();
unordered_set<T> s;
while (j < n) {
if (s.find(v[j]) == s.end()) {
s.insert(v[j]);
v[i++] = v[j];
}
j++;
}
v.resize(i);
}
int main() {
vector<int> v1{ 1,1,2,2,3,3,4,4,5,5 };
vector<char> v2{ 'a', 'b', 'c', 'c', 'd', 'd', 'e', 'e' };
vector<string> v3{ "hello", "world", "hello", "world", "hello" };
deleteRepeat(v1);
deleteRepeat(v2);
deleteRepeat(v3);
cout << "v1: ";
for (auto x : v1) cout << x << " ";
cout << endl;
cout << "v2: ";
for (auto x : v2) cout << x << " ";
cout << endl;
cout << "v3: ";
for (auto x : v3) cout << x << " ";
cout << endl;
return 0;
}
```
输出结果为:
```
v1: 1 2 3 4 5
v2: a b c d e
v3: hello world
```
可以看到,该算法成功地删除了顺序表中的重复元素,并且时间复杂度为O(n)。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)