C++实现整数排序去重的三种方法对比

这个问题要求对 `n` 个整数进行**排序并去重**，范围是 1~1000，n 最大为 99（因为第一行是 `1 < n < 100`，所以 n 至少是 2，最多 99）。 --- ## 🧠 思路分析 有几种常见解法： | 方案 | 思路 | 时间复杂度 | 适用场景 | |------|------|------------|----------| | **数组计数法**（桶排序） | 用一个大小为 1001 的布尔数组标记出现过的数字，然后按从小到大遍历输出 | O(n + 1000) | 非常适合，因为数值范围固定且不大 | | **排序 + 去重** | 用 `sort` 排序，再用 `unique` 去重 | O(n log n) | 通用，但本题用计数法更简单 | | **set容器** | 直接用 `std::set` 自动排序去重 | O(n log n) | 代码简洁，但稍慢 | 因为数值范围很小（1~1000），**计数法**是最优选择，代码简洁且高效。 --- ## 💻 C++ 实现（推荐计数法） ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; bool flag[1001] = {false}; // 标记某个数是否出现过 for (int i = 0; i < n; i++) { int x; cin >> x; flag[x] = true; // 标记出现 } bool first = true; for (int i = 1; i <= 1000; i++) { if (flag[i]) { if (!first) cout << " "; cout << i; first = false; } } cout << endl; return 0; } ``` ### 🔍 关键点解释： - `bool flag[1001]`：下标对应数值，`true` 表示该数出现过。 - 遍历 `1` 到 `1000` 自然就是从小到大，且天然去重。 - 输出时控制空格，避免多余空格。 --- ## 🧪 测试样例验证 **输入：** ``` 8 3 3 2 7 7 7 6 8 ``` **运行过程：** - 标记 `flag[3]`、`flag[2]`、`flag[7]`、`flag[6]`、`flag[8]` 为 true。 - 遍历 1~1000，输出 `2 3 6 7 8`。 **输出：** ``` 2 3 6 7 8 ``` 与题目完全一致 ✅ --- ## 📘 进阶建议 1. **如果数值范围更大**（比如 10^9），计数法不可行，改用 `std::set` 或先排序再 `unique`。 2. **如果输入可能有多余空格/换行**，`cin >> x` 会自动跳过空白字符，无需特殊处理。 3. **注意边界**：题目说 `1 < n < 100`，所以 n 至少为 2，不需要处理 n=1 的特殊情况，但代码也兼容。 4. **内存极小**：`bool` 数组才 1001 字节，完全符合题目 100MB 限制。 ### 🔁 备选方案：使用 `std::set`（代码更简洁） ```cpp #include <iostream> #include <set> using namespace std; int main() { int n, x; cin >> n; set<int> s; for (int i = 0; i < n; i++) { cin >> x; s.insert(x); } bool first = true; for (int v : s) { if (!first) cout << " "; cout << v; first = false; } cout << endl; return 0; } ``` > 这个方案代码更少，但效率略低（O(n log n)），对于本题完全可接受。 --- ## 📌 - **推荐使用计数法**，因为数值范围固定（1~1000），实现简单且时间复杂度为 O(n + 1000)，优于排序法。 - 注意输出格式：**数字之间用空格隔开，末尾不能有多余空格**。 - 这种“固定小范围数值去重排序”的问题，常见于编程竞赛入门题，掌握计数法能快速解决。 ######[AI写代码神器 | 994点数解答 | 2026-08-28 19:14:52]