CodeSignal上C++实现firstDuplicate函数执行超时的优化方法
现有代码超时的核心原因
当前实现的核心性能瓶颈来自于每遍历一个数组元素,都要对seen数组执行一次std::find线性查找,整体时间复杂度为O(n²)。当测试用例的数组规模较大时,累计的查找操作耗时会突破平台的执行时限要求。
同时代码末尾if (seen == a)的判断属于冗余操作,本身也会带来额外的O(n)遍历开销。
适配本题规则的最优优化方案
题目明确给定:数组元素的取值范围为1到数组长度的正整数,这个特性可以帮我们实现单次遍历完成判断、无需额外开辟存储空间的最优解,彻底解决超时问题:
- 核心逻辑:利用元素值本身作为数组的索引位置,通过修改对应位置数值的符号,记录某个值是否已经出现过
- 遍历规则:
- 取出当前元素的绝对值
val,因为遍历过程中可能已经把位置上的数值改成负数了,不能直接用原数值判断 - 检查
a[val - 1]位置的数值:如果是负数,说明这个值之前已经被标记过,当前位置就是它的第二次出现位置,直接返回val即可 - 如果是正数,说明这个值是第一次出现,把
a[val - 1]乘-1打上已读标记
- 取出当前元素的绝对值
- 遍历完整轮数组没有提前返回的话,直接返回-1即可
优化后的参考代码:
#include <vector> #include <cstdlib> int firstDuplicate(vector<int> a) { for (size_t i = 0; i < a.size(); ++i) { int val = abs(a[i]); // 对应位置已标记为负数,代表当前值是第二次出现 if (a[val - 1] < 0) { return val; } // 首次出现,打标记 a[val - 1] *= -1; } // 无重复值的场景 return -1; }
备选优化方案(不修改原数组场景)
如果业务场景不允许修改输入的原数组,可以把原本的线性查找的seen数组,替换为哈希集合unordered_set<int>存储已出现的元素:
- 每次判断当前元素是否已存在于哈希集合中,单次查找的时间复杂度为O(1),整体时间复杂度O(n),可以解决原有实现的超时问题
- 但这个方案需要额外的O(n)存储空间,还存在哈希冲突的额外开销,效率略低于上述的原地标记方案
内容的提问来源于stack exchange,提问作者thedro0-0
相关产品推荐
相关产品推荐

