连续相等数统计：从右向左遍历的 O(n) 高效解法

好的，这是一个非常经典的“连续相等数统计”问题。下面我会为你详细分析题目、提供多种语言的实现方案，并解释关键思路。 ## 🧠 题目理解与思路分析 题目的核心要求是： 1. 给定一个长度为 `n` 的整数序列。 2. 对于序列中的**每一个元素**，统计**从该元素开始，往右连续相等的元素个数**。 **举个例子**： - 序列：`3 2 2 2 7 7 7 7 7 6` - 对于第一个元素 `3`：从它开始往右看，只有它自己是3，所以连续个数是 `1`。 - 对于第二个元素 `2`：从它开始往右，有 `2, 2, 2` 三个连续相等的 `2`，所以是 `3`。 - 对于第三个元素 `2`：从它开始往右还有两个 `2`，所以是 `2`。 - 第四个元素 `2`：往后只剩自己，所以是 `1`。 - 第五个元素 `7`：往后有五个 `7`，所以是 `5` ... 以此类推。 **关键规律**： - 需要从右向左遍历，或者先统计每一段连续相等数的长度，然后从该段的左侧向右侧依次递减输出。 **高效解法**： 1. 从右向左遍历数组。 2. 如果当前元素与右边相邻元素相等，则 `count[i] = count[i+1] + 1`。 3. 否则，`count[i] = 1`。 这样一次遍历即可得到结果，时间复杂度 O(n)，空间复杂度 O(n)。 --- ## 🚀 代码实现 ### 1️⃣ C++ 实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } vector<int> result(n); result[n - 1] = 1; // 最后一个数连续个数为1 // 从右向左遍历 for (int i = n - 2; i >= 0; --i) { if (arr[i] == arr[i + 1]) { result[i] = result[i + 1] + 1; } else { result[i] = 1; } } // 输出结果 for (int i = 0; i < n; ++i) { cout << result[i]; if (i != n - 1) cout << " "; } cout << endl; return 0; } ``` --- ### 2️⃣ Python 实现 ```python n = int(input().strip()) arr = list(map(int, input().strip().split())) result = [0] * n result[-1] = 1 for i in range(n - 2, -1, -1): if arr[i] == arr[i + 1]: result[i] = result[i + 1] + 1 else: result[i] = 1 print(" ".join(map(str, result))) ``` --- ### 3️⃣ Java 实现 ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int[] result = new int[n]; result[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { if (arr[i] == arr[i + 1]) { result[i] = result[i + 1] + 1; } else { result[i] = 1; } } for (int i = 0; i < n; i++) { System.out.print(result[i]); if (i != n - 1) System.out.print(" "); } } } ``` --- ## 📌 关键点解析 | 概念 | 说明 | |------|------| | **从右向左遍历** | 这是解法的核心，利用了后一个元素的结果来推导前一个，避免了重复计算。 | | **边界处理** | 最后一个元素右侧没有元素，因此连续个数默认为1。 | | **输出格式** | 注意题目要求输出一行数字，中间用空格隔开，末尾无多余空格。 | --- ## 💡 进阶与优化建议 1. **空间优化**：如果不允许使用额外的数组，可以在原数组上直接修改，但会丢失原始数据。一般而言，本题允许 O(n) 辅助空间。 2. **性能考量**：由于 n < 100，任何 O(n^2) 的暴力解法也能通过，但上述 O(n) 解法是最优的。 3. **错误处理**： - 输入时有空格和换行，建议使用 `int` 读取，避免手动处理空格符。 - 确保 `n` 为有效数字，若 `n <= 0` 可提前返回空结果。 4. **扩展思考**： - 如果要求输出每个数**开始向左**连续相等的数，只需将遍历方向改为从左向右。 - 如果要求二维矩阵中每个位置向某个方向连续相等的个数，此思路也可扩展（如动态规划）。 --- ## 📚 学习资源推荐 - [C++ std::vector 官方文档](https://en.cppreference.com/w/cpp/container/vector) - [Python 列表操作指南](https://docs.python.org/3/tutorial/datastructures.html) - [Java 数组基础](https://docs.oracle.com/javase/tutorial/java/nutsandybars/arrays.html) --- ## ✅ 开发建议 - **测试边界**：建议测试 n=1、所有数相同、所有数不同、以及输入包含负数和零的情况。 - **代码风格**：保持变量命名清晰，避免单字母变量滥用（循环索引除外）。 - **提交前检查**：确保读取输入时不会遗漏末尾换行符，输出格式严格符合样例。 --- ######[AI写代码神器 | 1400点数解答 | 2026-07-24 20:33:30]