从信息学奥赛题到面试高频题：手把手教你用C++ STL的set和sort搞定数组去重-深圳市維司達科技有限公司

从竞赛到职场：C++ STL在数组去重中的实战艺术

在算法竞赛和编程面试的交汇处，数组去重问题像一座桥梁，连接着学术理论与工程实践。无论是信息学奥赛中要求高效处理大规模数据的场景，还是技术面试中考察候选人基本功的经典问题，"如何优雅地去除数组中的重复元素"始终是检验程序员基本功的试金石。今天，我们不只讨论解法，更要深入探索C++标准库中set和sort这对黄金组合在不同场景下的应用哲学。

1. 理解问题本质与需求边界

数组去重看似简单，实则隐藏着多个维度的考量。在实际编码前，我们需要明确几个关键问题：

是否需要保持原顺序：有些场景要求保留首次出现的元素（稳定去重），而有些只需要最终结果有序
数据规模与性能要求：1e5和1e6量级的数据对算法选择有决定性影响
内存限制：是否允许使用额外空间，直接影响我们能否使用哈希表等数据结构

考虑以下典型场景：

// 场景1：只需唯一值，不关心顺序 vector<int> arr1 = {3,1,2,2,4,3,5}; // 期望输出：{1,2,3,4,5}（顺序不限） // 场景2：需要保持首次出现顺序 vector<int> arr2 = {3,1,2,2,4,3,5}; // 期望输出：{3,1,2,4,5}

2. STL的set方案：简洁与效率的平衡

set是C++标准库提供的红黑树实现，天生具备自动去重和排序的特性。对于不要求保持原序的去重需求，它提供了最直观的解决方案。

2.1 基础用法与性能分析

vector<int> uniqueWithSet(const vector<int>& nums) { set<int> uniqueSet(nums.begin(), nums.end()); return vector<int>(uniqueSet.begin(), uniqueSet.end()); }

时间复杂度分析：

插入N个元素到set：O(N log N)
整体复杂度：O(N log N)

空间复杂度：O(N)（需要额外存储所有唯一元素）

注意：set方案在数据量超过1e6时可能成为性能瓶颈，因为红黑树的节点分配和平衡操作会带来不小的常数开销。

2.2 进阶技巧：unordered_set的应用

当不需要有序输出时，unordered_set能提供更优的平均时间复杂度：

vector<int> uniqueWithUnorderedSet(const vector<int>& nums) { unordered_set<int> uniqueSet(nums.begin(), nums.end()); return vector<int>(uniqueSet.begin(), uniqueSet.end()); }

性能对比表：

方法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否有序
set	O(N log N)	O(N log N)	O(N)	是
unordered_set	O(N)	O(N²)	O(N)	否
sort+unique	O(N log N)	O(N log N)	O(1)	是

3. sort与unique组合：原地算法的艺术

对于内存敏感的场景，或者需要最小化额外空间使用的需求，sort和unique的组合提供了近乎完美的解决方案。

3.1 经典实现与原理

vector<int> uniqueWithSort(vector<int> nums) { sort(nums.begin(), nums.end()); auto last = unique(nums.begin(), nums.end()); nums.erase(last, nums.end()); return nums; }

关键点解析：

sort将相同元素排列在一起，复杂度O(N log N)
unique将不重复元素移到前部，返回新的逻辑结尾，复杂度O(N)
erase删除尾部重复元素，复杂度O(N)

提示：这种方法修改了原始数组的顺序，如果需要保持原序，此方案不适用。

3.2 性能优化技巧

对于特定数据特征，我们可以进行优化：

// 优化1：提前检查是否已排序 vector<int> uniqueOptimized(vector<int> nums) { if (!is_sorted(nums.begin(), nums.end())) { sort(nums.begin(), nums.end()); } nums.erase(unique(nums.begin(), nums.end()), nums.end()); return nums; } // 优化2：利用已排序区间 vector<int> mergeAndUnique(const vector<vector<int>>& sortedArrays) { vector<int> merged; for (const auto& arr : sortedArrays) { merged.insert(merged.end(), arr.begin(), arr.end()); } sort(merged.begin(), merged.end()); merged.erase(unique(merged.begin(), merged.end()), merged.end()); return merged; }

4. 实战场景分析与选择策略

不同的应用场景需要不同的去重策略，我们通过几个典型案例来说明如何做出合理选择。

4.1 小规模数据（N ≤ 1e4）

对于小规模数据，代码简洁性比微小的性能差异更重要：

// 最简单清晰的写法 set<int> uniqueSet(arr.begin(), arr.end()); vector<int> result(uniqueSet.begin(), uniqueSet.end());

4.2 中大规模数据（1e4 < N ≤ 1e6）

此时需要考虑内存局部性和缓存命中率：

// 优先考虑sort+unique方案 sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end());

4.3 超大规模数据（N > 1e6）

可能需要分块处理或并行算法：

// 并行去重示例（C++17并行算法） vector<int> parallelUnique(vector<int> arr) { sort(execution::par, arr.begin(), arr.end()); arr.erase(unique(execution::par, arr.begin(), arr.end()), arr.end()); return arr; }

场景决策矩阵：

场景特征	推荐方案	理由
数据量小，需要代码简洁	set	代码最简洁
数据量大，内存充足	unordered_set	平均O(N)时间复杂度
数据量大，内存受限	sort+unique	原地操作，空间复杂度O(1)
需要保持原始顺序	顺序遍历+哈希表	牺牲时间换顺序保持
数据基本有序	优化版sort+unique	利用已有顺序减少操作

5. 面试中的深度考察点

技术面试中，数组去重问题常常作为引子，考察候选人对以下方面的理解：

5.1 迭代器失效问题

// 错误示范：在遍历时删除元素 for (auto it = arr.begin(); it != arr.end(); ++it) { if (some_condition) { arr.erase(it); // 危险！迭代器失效 } } // 正确做法 auto new_end = remove_if(arr.begin(), arr.end(), [](int x) { return some_condition(x); }); arr.erase(new_end, arr.end());

5.2 自定义类型的去重

对于自定义类型，需要提供比较准则或哈希函数：

struct Point { int x, y; bool operator<(const Point& other) const { return tie(x, y) < tie(other.x, other.y); } }; // set用法 set<Point> points; // unordered_set需要自定义哈希 struct PointHash { size_t operator()(const Point& p) const { return hash<int>()(p.x) ^ hash<int>()(p.y); } }; unordered_set<Point, PointHash> uniquePoints;

5.3 稳定性与扩展性讨论

面试中常被问到的进阶问题：

如何实现稳定去重（保留首次出现的元素）？
如果内存不足，如何处理超大规模数据的去重？
分布式环境下如何实现去重？

// 稳定去重实现 vector<int> stableUnique(const vector<int>& arr) { vector<int> result; unordered_set<int> seen; for (int num : arr) { if (seen.insert(num).second) { result.push_back(num); } } return result; }