企业官网建设流程全解析

整数去重算法实战：从暴力循环到哈希优化的三种策略对比

在编程竞赛和日常开发中，数据去重是一个高频出现的需求。以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; // 标记重复元素 } } } }

这种方法的原理很简单：

1. 外层循环遍历每个元素
2. 内层循环检查后续是否有相同元素
3. 发现重复时，将后续元素标记为0（题目保证输入都是≥10的数）

时间复杂度分析：最坏情况下（无重复元素），需要执行n(n-1)/2次比较，时间复杂度为O(n²)。对于n=20000的情况，这意味着约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无关

性能对比：

在实际测试中，当n=20000时，哈希法的执行时间通常是暴力法的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)（递归栈）

适用场景分析：

1. 当题目允许改变元素顺序时
2. 当需要去重后进一步处理（如统计频率）时
3. 当数值范围很大（无法使用哈希法）时

注意：在SWUST OJ 1190中，题目明确要求保持原始顺序，因此这种方法不适用。但在其他允许改变顺序的场景中，它可能是更好的选择。

4. 进阶讨论：通用哈希解法

对于数值范围未知的情况（如整数范围很大或不确定），我们可以使用更通用的哈希表实现。C++中可以使用unordered_set，C语言可以自己实现简单的哈希表：

#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)，比固定数组更灵活

实际应用建议：

1. 如果数值范围已知且较小（如本题的10-100），优先使用数组标记法
2. 如果数值范围大但重复率高，哈希表更节省空间
3. 如果允许改变顺序且需要后续处理，考虑排序法

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. 测试用例设计与边界考虑

完善的算法实现需要处理各种边界情况：

1. 极端输入测试：

   • n=1的最小输入
   • n=20000的最大输入
   • 全部元素相同的情况
   • 无重复元素的情况

2. 性能测试：

// 生成最坏情况测试数据（无重复） for (i = 0; i < 20000; i++) { a[i] = i + 10; // 保证在10-20009范围内 }

3. 随机测试：

srand(time(NULL)); for (i = 0; i < n; i++) { a[i] = rand() % 91 + 10; // 10-100的随机数 }

在实际编码比赛中，我通常会先写暴力解法确保正确性，再逐步优化。对于哈希解法，特别注意处理冲突的方式会影响实际性能。当使用链地址法时，选择一个合适的哈希表大小和哈希函数至关重要。