统计左侧小于当前元素个数 - 暴力解法与进阶思路

这道题是一个典型的**“统计左侧小于当前元素的个数”**问题。 题目要求对每个位置，统计它**左边**有多少个数字比它小。 --- ## ✅ 题目分析 - 输入：第一行是整数 n，第二行是 n 个整数。 - 输出：一行 n 个整数，第 i 个数表示原数组第 i 个元素左边有多少个元素小于它。 - 限制：n < 100，直接暴力即可。 --- ## 🧠 解题思路 最简单的思路是**双重循环**： 1. 外层循环遍历每个元素 `arr[i]` 2. 内层循环从 `0` 到 `i-1`，统计小于 `arr[i]` 的元素个数 3. 将统计结果存入结果数组 因为 n < 100，时间复杂度 O(n²) 完全可行。 --- ## 💻 代码实现（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, 0); for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { count++; } } result[i] = count; } for (int i = 0; i < n; i++) { cout << result[i]; if (i != n - 1) cout << " "; } cout << endl; return 0; } ``` --- ## 📘 代码解释 | 部分 | 说明 | |------|------| | `vector<int> arr(n)` | 动态数组，存储输入的数字 | | `vector<int> result(n, 0)` | 结果数组，初始化为 0 | | 外层循环 `for (int i = 0; i < n; i++)` | 遍历每个元素 | | 内层循环 `for (int j = 0; j < i; j++)` | 遍历当前元素左边所有元素 | | `if (arr[j] < arr[i]) count++` | 如果左边元素小于当前元素，计数+1 | | 结果输出 | 用空格分隔，末尾无多余空格 | --- ## ✅ 输入输出示例验证 输入： ``` 6 4 3 0 5 1 2 ``` 过程： - `4`：左边无元素 → 0 - `3`：左边 4 > 3 → 0 - `0`：左边 4,3 均 > 0 → 0 - `5`：左边 4,3,0 均 < 5 → 3 - `1`：左边 0 < 1 → 1 - `2`：左边 0,1 < 2 → 2 输出： ``` 0 0 0 3 1 2 ``` --- ## 📌 开发建议 1. **注意边界条件**：当 n=1 时，输出应为 `0` 2. **换行处理**：输出结束后记得换行 3. **可以使用 `printf / scanf`** 提高输入输出速度，但本题数据量小，`cin / cout` 足够 4. **可扩展**：如果 n 很大（比如 10^5），则需要使用**树状数组/线段树**优化到 O(n log n) --- ## 🔄 进阶思考（可选阅读） 如果 n 很大（如 10^5），暴力 O(n²) 会超时，此时可以使用： - **树状数组（Fenwick Tree）**：将值离散化后，每个元素插入时查询小于它的个数 - **线段树**：同理，维护区间和 - **归并排序计数**：在归并过程中统计右侧小于左侧的个数（与本题方向相反） --- ######[AI写代码神器 | 909点数解答 | 2026-07-24 19:43:42]