C++ 统计左侧更小元素个数的解决方案及优化

好的，没问题！这是一道经典的“统计左侧比自己小的元素个数”问题，非常适合用C++高效解决。 ### 🧠 问题分析 对于每一条鱼（数组中的第 `i` 个元素），我们需要统计它**左边**所有鱼中，**可爱程度严格小于**它的鱼的数量。 * **输入**：`n` 只鱼的可爱程度数组 `a`。 * **输出**：一个数组 `result`，其中 `result[i]` 表示第 `i` 条鱼眼中不如自己可爱的鱼数。 ### 💻 解决方案：双重循环（暴力法） 最直接的方法就是对于每一条鱼，遍历它左边的所有鱼，统计有多少条比它小。 虽然时间复杂度为 O(n²)，但对于题目没有明确说明数据范围的情况（通常 n ≤ 5000 可以接受），这是一个正确且易于理解的解法。 #### 👣 算法步骤 1. 读取整数 `n`。 2. 读取并存储数组 `a`（大小为 n）。 3. 创建一个大小为 n 的结果数组 `result`。 4. 遍历每条鱼 `i`（从 0 到 n-1）。 5. 初始化 `count = 0`。 6. 遍历 `i` 左边的鱼 `j`（从 0 到 i-1），如果 `a[j] < a[i]`，则 `count++`。 7. 将 `count` 存入 `result[i]`。 8. 输出 `result` 数组，元素之间用空格分隔。 #### 📝 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> result(n, 0); // 外层循环：当前鱼 for (int i = 0; i < n; i++) { int count = 0; // 内层循环：左侧的鱼 for (int j = 0; j < i; j++) { if (a[j] < a[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> a(n)`**：使用动态数组 `vector` 来存储可爱程度，可以根据输入的 `n` 动态分配大小，更灵活安全。 - **双重循环结构**： - 外层循环 `for (int i = 0; i < n; i++)` 代表当前要计算的鱼。 - 内层循环 `for (int j = 0; j < i; j++)` 只遍历当前鱼左边的鱼，确保只计算“眼力范围内”的鱼。 这是正确性的关键。 - **严格小于的判断**：`if (a[j] < a[i])` 只统计**严格小于**的鱼，不包含等于，符合题意“不如自己可爱”。 ### ⚡ 进阶优化：树状数组 / 线段树 如果数据规模很大（例如 n ≤ 10⁵），O(n²) 的算法会超时。此时可以使用**树状数组**或**线段树**来优化到 O(n log n)。 #### 🧩 思路 1. **离散化**：由于可爱程度是整数，但可能很大（比如 10⁹），我们需要将所有不同的可爱程度映射到连续的整数编号（1, 2, 3, ...）。 2. **树状数组**：维护一个树状数组 `BIT`，用于快速统计当前已经出现过的、比某个值小的元素个数。 3. **遍历**： - 从左到右遍历每条鱼。 - 对于当前鱼的可爱程度 `x`（离散化后的编号），查询 `BIT` 中 `1` 到 `x-1` 的和，这就是比它小的鱼的数量。 - 将结果存入数组。 - 将当前鱼的编号 `x` 加入 `BIT`（即 `BIT[x] += 1`）。 这种优化方法常用于解决“逆序对”相关的问题。 ### 🚀 开发建议 & 常见陷阱 1. **理解题意**：确保“不如自己可爱”是指**严格小于**，而不是小于等于。代码中的判断条件要准确。 2. **输入输出格式**：严格按照题目要求，输出数据之间用**空格**分隔，最后通常要求有换行符 `\n`。 3. **数组边界**：在使用嵌套循环时，确保内层循环的终止条件是 `j < i`，而不是 `j <= i`，因为鱼不能看到自己。 4. **性能分析**：在编写代码前，先评估数据规模。如果 `n` 很大（如 > 10⁵），应优先考虑更高效的算法，避免在面试或竞赛中失分。 5. **代码复用**：可以将计算逻辑封装成一个函数，提高代码的可读性和可测试性。 ######[AI写代码神器 | 1180点数解答 | 2026-05-23 14:48:26]