数组可任意重排,求重排后"相邻恰差 1"的子数组最长长度。
对于 k 个整数构成的数组 [b₁, b₂, …, b_k],如果对任意 1 ≤ i < k 都有 b(i+1) = b(i) + 1,则称它是一个连续段。
给定数组 a,你可以任意重排它的元素顺序。问重排后,所有是连续段的子数组中,最长的长度是多少。
重排去重连续整数区间排序
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个整数 |
| 输出 | 重排后最长连续段的长度 |
| 数据范围 | n ≤ 10⁵ |
| 数值范围 | −10⁹ ≤ aᵢ ≤ 10⁹,可能为负 |
| 子数组 | 必须下标连续;重排指的是先重排整个数组再取子数组 |
先看"重排"能带来什么,再把它转化成找连续区间。
原数组里 0、1、2 是连续的,但 4 插在中间
重排成 [4, 0, 1, 2] 后,后半段 0、1、2 就成了连续段
所以答案是 3
✅ 3
数组里的数去重后是 {0, 1, 2, 4}
其中 0、1、2 是连续的一段(长度 3)
4 单独一个,不接前面(2 和 4 之间缺了 3)
✅ 最长连续区间长度 = 3
| 排序去重后 | 相邻差 | 是否连续 |
|---|---|---|
| 0 | — | 起点 |
| 1 | 1 | ✅ 连续 |
| 2 | 1 | ✅ 连续 |
| 4 | 2 | ❌ 断了 |
最长链:0 → 1 → 2,长度 3 ✓
这组数据里有很多重复(9 出现 2 次、4 出现 2 次、3 出现 2 次),正好考察"去重"。
| 步骤 | 内容 | 说明 |
|---|---|---|
| 原数组 | 9, 9, 8, 2, 4, 4, 3, 5, 3 | 有重复元素 |
| 排序 | 2, 3, 3, 4, 4, 5, 8, 9, 9 | 相同元素相邻 |
| 去重 | 2, 3, 4, 5, 8, 9 | 重复的只保留一个 |
| 找最长连续区间 | 2 → 3 → 4 → 5(长度 4) | 8、9 是另一段(长度 2) |
答案 4 ✓
排序后扫一遍,跳过重复元素,统计相邻差 1 的最长链
a[i] == a[i-1] 就跳过(去重);如果 a[i] == a[i-1] + 1 就让链长加一;否则链长重置为 1。把数放进 set,只从"x−1 不在 set 中"的数开始往后数
| 方案 | 时间复杂度 | 代码量 |
|---|---|---|
| 排序 + 扫描 | O(n log n) | 约 10 行 |
| set 起点法 | 期望 O(n) | 约 18 行 |
输入一组整数,程序会排序去重并找出最长的连续整数区间。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[100005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); sort(a, a + n); // 排序后相同元素相邻,便于去重 int best = 1, cur = 1; for (int i = 1; i < n; i++) { if (a[i] == a[i - 1]) continue; // 重复元素跳过(相当于去重) if (a[i] == a[i - 1] + 1) cur++; // 恰好差 1,链延长 else cur = 1; // 断了,重新开始 if (cur > best) best = cur; } printf("%d\n", best); return 0; }
a[i] == a[i-1] 时直接 continue,既不重置链长、也不延长,效果等同于"把重复元素删掉"。这比先手动 unique 再扫描更简洁。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
sort(a, a + n) | 排序 | 让相同元素相邻,也让连续数相邻 |
if (a[i] == a[i-1]) continue; | 去重 | 跳过重复,不影响当前链长 |
if (a[i] == a[i-1] + 1) cur++; | 链延长 | 必须是恰好差 1 |
else cur = 1; | 链重置 | 新的一段从这里开始 |
[3, 3, 4] 会被误算成 3;② 把"差恰好 1"写成"差不大于 1",那样 [3, 3] 也会被算成长度 2;③ best 初始化为 0:当 n = 1 时会输出 0,应该是 1。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 3 | 题面样例 1 |
9 | 4 | 题面样例 2(含大量重复) |
1 | 1 | 单元素,长度为 1 |
3 | 2 | 必须去重:答案是 3、4 长度 2 |
3 | 1 | 全相同,去重后只剩 1 个 |
5 | 5 | 排序后恰好是 1~5,答案 5 |
4 | 3 | 负数同样适用,−3、−2、−1 连续 |
需要存下整个数组。
✅ 10⁵ 规模排序加扫描,瞬间完成。
// 去重的三种写法 // 1) 排序 + 扫描时跳过(本题用法,最省事) // 2) 排序 + unique sort(a, a + n); int m = unique(a, a + n) - a; // m 是去重后的长度 // 3) 用 set 自动去重(值域大或稀疏时用) set<long long> s(a, a + n); for (long long x : s) { /* 已升序且无重复 */ } // 找最长连续整数区间的"起点法"(不排序) set<long long> st(a, a + n); int best = 1; for (long long x : st) { if (st.count(x - 1)) continue; // 不是链起点,跳过 long long y = x; while (st.count(y + 1)) y++; best = max(best, (int)(y - x + 1)); }
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 重排问题转化 | 把"可重排"理解为"自由挑子集" | 所有"可重排后求最优"的题目 |
| 去重必要性 | 连续段内不能有重复 | 严格递增/递减序列类问题 |
| 排序 + 扫描 | 相邻元素比较 | 求最长连续、最长递增子序列(简化版) |