You need to enable JavaScript to run this app. CodeSignal上C++实现firstDuplicate函数执行超时的优化方法
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.11 01:45:07