AcWing 799. 最长连续不重复子序列
时间: 2023-05-23 14:04:46 浏览: 117
A:
题目描述
给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续子序列,输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数(均在0~10^4范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。
数据范围
1≤n≤10^5
输入样例:
5
1 2 3 2 5
输出样例:
3
算法
(滑动窗口) $O(n)$
时间复杂度
参考文献
Python 代码
C++ 代码
java 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
AcWing 839. 堆排序
堆排序是一种基于堆数据结构的排序算法。它通过将待排序的序列构建成一个大顶堆(或小顶堆),然后依次将堆顶元素与最后一个元素交换,并重新调整堆,直到整个序列有序。
具体的堆排序算法如下:
1. 构建初始堆:将待排序序列构建成一个大顶堆。从最后一个非叶子节点开始,依次向前调整每个节点,使其满足大顶堆的性质。这一过程称为“下沉”操作。
2. 将堆顶元素与最后一个元素交换:将堆顶元素与待排序序列的最后一个元素进行交换,此时最后一个元素即为当前序列的最大值。
3. 重新调整堆:将交换后的堆顶元素进行“下沉”操作,使其满足大顶堆的性质。
4. 重复步骤2和3,直到整个序列有序。
下面是C++实现堆排序的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 下沉操作
void heapify(vector<int>& nums, int n, int i) {
int largest = i; // 初始化最大值为当前节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点大于根节点,则更新最大值
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
// 如果右子节点大于最大值,则更新最大值
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
// 如果最大值不是当前节点,则交换节点,并继续调整堆
if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}
// 堆排序
void heapSort(vector<int>& nums) {
int n = nums.size();
// 构建初始堆,从最后一个非叶子节点开始向前调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
// 依次将堆顶元素与最后一个元素交换,并重新调整堆
for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]);
heapify(nums, i, 0);
}
}
int main() {
vector<int> nums = {4, 2, 6, 8, 5, 7};
heapSort(nums);
cout << "Sorted array: ";
for (int num : nums) {
cout << num << " ";
}
return 0;
}
```
以上是堆排序的C++实现代码,通过构建初始堆和重复交换堆顶元素的过程,最终实现了对序列的排序。时间复杂度为O(nlogn),其中n是序列的长度。
AcWing 838. 堆排序
堆排序是一种高效的排序算法,它利用了堆的数据结构来实现排序。堆是一个完全二叉树,具有以下性质:对于任意节点 i,其父节点的值小于等于子节点的值。
堆排序的基本思路如下:
1. 构建最大堆:将待排序的数组看作是一个完全二叉树,从最后一个非叶子节点开始,依次向上调整每个节点,使得以该节点为根的子树满足最大堆的性质。
2. 将堆顶元素与最后一个元素交换:将最大堆的堆顶元素(即数组的第一个元素)与数组最后一个元素交换位置,此时最大元素就位于数组的最后。
3. 调整堆:将剩余元素重新调整为最大堆。
4. 重复步骤 2 和步骤 3,直到所有元素都排序完成。
以下是堆排序的 C++ 代码实现:
```cpp
#include <iostream>
using namespace std;
// 调整以 root 为根的子树为最大堆
void heapify(int arr[], int n, int root) {
int largest = root; // 假设根节点最大
int left = 2 * root + 1; // 左子节点索引
int right = 2 * root + 2; // 右子节点索引
// 若左子节点大于根节点,更新最大值索引
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 若右子节点大于最大值节点,更新最大值索引
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 若最大值不是根节点,交换根节点和最大值
if (largest != root) {
swap(arr[root], arr[largest]);
// 递归调整交换后的子树
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐步取出最大值,调整堆
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
以上就是堆排序的基本思路和实现方法。堆排序的时间复杂度为 O(nlogn),其中 n 为数组的长度。