输入一个长度为n的序列,找到一个尽量长的连续子序列Al-Ar,使得该序列中没有相同元素。用C++语言编程实现,加上可视化效果
时间: 2024-03-07 08:48:56 浏览: 110
用C++实现各种排序算法
以下是C++代码实现:
```c++
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<int> longest_unique_subarray(const vector<int>& arr) {
int n = arr.size();
vector<int> res;
map<int, int> idx;
int i = 0, j = 0;
while (j < n) {
if (idx.count(arr[j]) && idx[arr[j]] >= i) {
i = idx[arr[j]] + 1;
}
idx[arr[j]] = j;
if (j - i + 1 > res.size()) {
res = {i, j};
}
++j;
}
return res;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50};
arr[5] = 1;
arr[35] = 2;
auto res = longest_unique_subarray(arr);
for (int i = res[0]; i <= res[1]; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
以上代码实现了一个找到最长无重复子序列的函数longest\_unique\_subarray,使用了一个map来存储元素的下标,以便快速查询是否有重复元素。主函数中给出了一个测试用例,其中数组中的第6个和第36个元素重复出现了,输出的结果为1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35。
阅读全文