C++实现指定范围整数排序去重的桶排序算法详解

这个问题是一个典型的**排序+去重**问题。由于数据范围很小（n<100，数值1~1000），我们有多种高效解法。以下是C++的完整解决方案和详细讲解。 ## 🧠 解题思路分析 **核心要点**： - **排序**：从小到大排列所有数字 - **去重**：删除重复元素，只保留一个 - **输出格式**：空格分隔，末尾无多余空格 **推荐方法**：由于数值范围固定（1~1000），可以使用**桶排序/计数排序**思想，一次性完成排序+去重，时间复杂度O(n)，效率最高。 ## 💻 C++ 完整代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; // 使用数组记录每个数字是否出现过（桶排序思想） bool seen[1001] = {false}; // 下标1~1000，初始全为false // 读取n个数，标记出现过的数字 for (int i = 0; i < n; i++) { int num; cin >> num; seen[num] = true; // 标记该数字出现过（自动去重） } // 从小到大遍历1~1000，输出所有出现过的数字 bool first = true; // 控制空格输出 for (int i = 1; i <= 1000; i++) { if (seen[i]) { if (!first) { cout << " "; // 非第一个数字前加空格 } cout << i; first = false; } } cout << endl; return 0; } ``` ## 🔍 代码逐段解析 **核心机制**： 1. **`bool seen[1001]`**：用布尔数组记录每个数字是否出现过。当输入数字`num`时，将`seen[num]`设为`true`，这天然实现了**去重**（重复数字第二次出现不会改变数组值）。 2. **遍历输出**：从1到1000顺序检查，若`seen[i]`为`true`则输出`i`。由于遍历顺序是从小到大，**排序自动完成**。 3. **空格控制**：使用`first`变量标记是否为第一个输出数字，避免末尾多余空格。 ## ✅ 测试验证 **输入样例**： ``` 8 3 3 2 7 7 7 6 8 ``` **执行过程**： - 读取`3` → `seen[3]=true` - 读取`3` → `seen[3]`已为true，无变化（去重） - 读取`2` → `seen[2]=true` - 读取`7` → `seen[7]=true` - 读取`7` → 无变化 - 读取`7` → 无变化 - 读取`6` → `seen[6]=true` - 读取`8` → `seen[8]=true` **输出结果**： ``` 2 3 6 7 8 ``` 与题目要求完全一致 ✅ ## ⚡ 其他解法对比 | 方法 | 代码实现 | 时间复杂度 | 适用场景 | |------|---------|-----------|---------| | **桶排序（本方案）** | 简单 | O(n + 1000) | 数值范围固定且较小 | | **sort + unique** | 使用STL | O(n log n) | 通用性强，数据量大或范围未知 | | **set容器** | 使用set | O(n log n) | 自动排序+去重，简洁 | **备选方案（sort+unique）**： ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; sort(v.begin(), v.end()); // 排序 auto it = unique(v.begin(), v.end()); // 去重（相邻重复元素移除） v.erase(it, v.end()); // 删除多余元素 for (int i = 0; i < v.size(); i++) { if (i > 0) cout << " "; cout << v[i]; } cout << endl; return 0; } ``` ## 📌 关键提示 - **内存优化**：`seen[1001]`仅占用约1KB，完全满足100MB限制 - **边界处理**：题目规定1~1000范围，数组下标从1开始使用即可 - **性能**：桶排序时间复杂度O(n)，远优于排序算法，在处理大量数据时优势明显 - **可读性**：变量命名清晰（`seen`表示是否出现过），逻辑直观 **时间复杂度**：O(n + 1000) ≈ O(n)，其中n为输入个数 **空间复杂度**：O(1001) ≈ O(1)，常数级额外空间 这种解法非常适合数值范围受限的排序去重问题，是竞赛和开发中的常用技巧。 ######[AI写代码神器 | 1145点数解答 | 2026-08-15 20:09:20]