C++ 数组中寻找不重复的数字-C++-PHP中文网

std::unordered_set 是去重首选，平均 o(1) 时间复杂度；需保持首次出现顺序时用 std::unordered_map 记录位置或额外 vector；值域有限可用计数数组；std::unique 仅适用于已排序数组。

c++ 数组中寻找不重复的数字

如果数组里只有少量重复、且不要求保持原始顺序，std::unordered_set 是最直接的选择。它平均 O(1) 插入和查找，比排序再扫一遍更轻量。

常见错误是误用 std::set——它自动排序且 O(log n) 插入，纯为去重时没必要引入额外开销和顺序干扰。

遍历原数组，对每个 num 尝试插入 seen.insert(num)，返回值 pair<iterator bool></iterator> 的 second 为 true 表示首次插入
只在 second == true 时把 num 推入结果容器（如 std::vector），避免重复添加
注意：unordered_set 不保证遍历顺序，若需按首次出现顺序保留，得额外记录索引或改用 std::map<int int></int> 记录首次位置

很多实际场景（比如日志去重、用户行为序列）要求结果和原数组中“第一次出现”的顺序一致。这时不能只靠集合判重，得记下每个数的首次索引。

用 std::map<int int></int> 存 {value → first_index}，配合一个 std::vector 收集结果，就能单趟完成：

遍历时检查 first_seen.find(num) == first_seen.end()，成立说明是首次遇到
如果是首次，执行 first_seen[num] = i 并 result.push_back(num)
别用 std::unordered_map 替代——虽然平均快，但 C++ 标准不保证遍历顺序，而 std::map 按 key 排序，这里不需要；真正要的是插入顺序不可控，所以仍推荐 std::unordered_map + 额外 vector 记顺序，或者干脆用 std::vector + std::find（小数组可行）

当明确知道所有数字都在小范围内（比如 0~1000 或 -1000~1000），用 std::vector<bool></bool> 或 std::vector<int></int> 当计数数组，比哈希表更快更省内存。

下载

典型坑是没处理负数偏移——比如值域是 [-500, 500]，就得开大小为 1001 的数组，并把 num 映射到 num + 500 索引。

先遍历一次统计频次：count[num + offset]++
再遍历原数组，对每个 num 检查 count[num + offset] == 1，成立则加入结果
注意：这种方法只适合找“出现恰好一次”的数（即真·不重复），不是“去重”；标题说“不重复的数字”，语义模糊，需确认需求——是“去重后唯一值”还是“只出现一次的值”

std::unique 只移除**连续重复**元素，不是全局去重。直接在乱序数组上调用，结果完全不可靠。

有人试过先 std::sort 再 std::unique，虽能实现去重，但代价高（O(n log n)）且破坏原始顺序，还得多写几行 erase-unique 惯用法：

std::sort(arr.begin(), arr.end());
auto last = std::unique(arr.begin(), arr.end());
arr.erase(last, arr.end());

这适合你明确接受排序副作用的场景，比如预处理静态配置数据；否则不如用 unordered_set 方案。

真正容易被忽略的是：题目说“寻找不重复的数字”，没说是否允许修改原数组、是否关心内存分配次数、是否后续还要用原顺序——这些细节决定方案选型，而不是一上来就套模板。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！

C++ 数组中寻找不重复的数字