整数去重算法实战从暴力循环到哈希优化的三种策略对比在编程竞赛和日常开发中数据去重是一个高频出现的需求。以SWUST OJ 1190题为例这道看似简单的整数去重问题实际上隐藏着算法优化的精髓。本文将带你深入剖析三种不同层级的解法从时间复杂度O(n²)的暴力循环到O(n)的哈希优化再到排序法的取舍让你彻底掌握根据场景选择最优解的能力。1. 问题分析与暴力解法题目要求我们对一个整数序列进行去重操作保留每个数字第一次出现的位置。给定的约束条件是n≤20000数值范围在10到100之间。这个数值范围的特殊性为我们后续的优化提供了重要线索。先来看最直观的暴力解法——双重循环标记法for (i 0; i n; i) { if (a[i] 0) { for (j i 1; j n; j) { if (a[i] a[j]) { a[j] 0; // 标记重复元素 } } } }这种方法的原理很简单外层循环遍历每个元素内层循环检查后续是否有相同元素发现重复时将后续元素标记为0题目保证输入都是≥10的数时间复杂度分析最坏情况下无重复元素需要执行n(n-1)/2次比较时间复杂度为O(n²)。对于n20000的情况这意味着约2亿次操作这在OJ系统中很可能导致超时。空间复杂度O(1)除了输入数组外不需要额外空间。提示虽然这种解法在n较小时可行但当n接近20000时性能会急剧下降。这是我们需要考虑更优解法的根本原因。2. 哈希表优化空间换时间的艺术利用题目中数值范围在10到100之间这一关键条件我们可以设计出更高效的算法。因为数值范围有限仅91种可能值我们可以使用一个布尔数组来记录数字是否已经出现过bool appeared[101] {false}; // 10-100的标记数组 for (i 0; i n; i) { if (!appeared[a[i]]) { appeared[a[i]] true; printf(%d , a[i]); } }这种方法的核心优势时间复杂度降至O(n)只需遍历数组一次空间复杂度O(1)虽然使用了额外数组但其大小固定为101与n无关性能对比方法时间复杂度空间复杂度n20000时的操作次数暴力循环O(n²)O(1)~200,000,000哈希标记法O(n)O(1)~20,000在实际测试中当n20000时哈希法的执行时间通常是暴力法的1/10000左右。这种优化在算法竞赛中常常是能否AC的关键。3. 排序去重法的取舍另一种常见的去重思路是先排序再去重。这种方法在某些场景下也很有效// 假设已实现快速排序 quickSort(a, 0, n-1); printf(%d, a[0]); for (i 1; i n; i) { if (a[i] ! a[i-1]) { printf( %d, a[i]); } }这种方法的特点时间复杂度O(nlogn)主要来自排序空间复杂度取决于排序算法通常为O(1)原地排序或O(logn)递归栈适用场景分析当题目允许改变元素顺序时当需要去重后进一步处理如统计频率时当数值范围很大无法使用哈希法时注意在SWUST OJ 1190中题目明确要求保持原始顺序因此这种方法不适用。但在其他允许改变顺序的场景中它可能是更好的选择。4. 进阶讨论通用哈希解法对于数值范围未知的情况如整数范围很大或不确定我们可以使用更通用的哈希表实现。C中可以使用unordered_setC语言可以自己实现简单的哈希表#define TABLE_SIZE 10007 // 选择一个质数作为哈希表大小 struct HashNode { int key; struct HashNode* next; }; struct HashTable { struct HashNode* table[TABLE_SIZE]; }; // 哈希函数示例 int hash(int key) { return key % TABLE_SIZE; } // 检查并插入哈希表 bool checkAndInsert(struct HashTable* ht, int key) { int hash_val hash(key); struct HashNode* node ht-table[hash_val]; while (node ! NULL) { if (node-key key) { return true; // 已存在 } node node-next; } // 插入新节点 struct HashNode* newNode (struct HashNode*)malloc(sizeof(struct HashNode)); newNode-key key; newNode-next ht-table[hash_val]; ht-table[hash_val] newNode; return false; // 不存在 }这种方法的优势在于适用于任何整数范围平均时间复杂度仍为O(n)空间复杂度O(n)比固定数组更灵活实际应用建议如果数值范围已知且较小如本题的10-100优先使用数组标记法如果数值范围大但重复率高哈希表更节省空间如果允许改变顺序且需要后续处理考虑排序法5. 工程实践中的优化技巧在实际项目开发中我们还需要考虑更多因素内存局部性优化// 更好的循环方式提高缓存命中率 for (i 0; i n; i) { if (a[i] 0) { int target a[i]; for (j i 1; j n; j) { if (a[j] target) { a[j] 0; } } } }并行化可能性哈希法天然适合并行处理可以分块处理数组最后合并结果语言特性利用C中使用unordered_set更简洁Python可利用集合(set)特性一行代码实现# Python示例 def remove_duplicates(arr): seen set() return [x for x in arr if not (x in seen or seen.add(x))]6. 测试用例设计与边界考虑完善的算法实现需要处理各种边界情况极端输入测试n1的最小输入n20000的最大输入全部元素相同的情况无重复元素的情况性能测试// 生成最坏情况测试数据无重复 for (i 0; i 20000; i) { a[i] i 10; // 保证在10-20009范围内 }随机测试srand(time(NULL)); for (i 0; i n; i) { a[i] rand() % 91 10; // 10-100的随机数 }在实际编码比赛中我通常会先写暴力解法确保正确性再逐步优化。对于哈希解法特别注意处理冲突的方式会影响实际性能。当使用链地址法时选择一个合适的哈希表大小和哈希函数至关重要。