求首个缺失正整数：寻求无排序的O(n)优化方案

问题背景 #

给定一个包含正负整数的列表，需要返回其中首个缺失的正整数。现有实现方案存在优化空间，询问是否存在无需排序的O(n)时间复杂度方案；若不存在，希望得到其他优化方案。

示例 #

• 输入：3 -1 1 0 4，预期输出：2
• 输入：-1 -4 -3，预期输出：1
• 输入：1 3 2，预期输出：4

现有解决方案代码 #

f: {if[all x<1;:1]; x: asc x where x>0;  b:1+first where not x=1+til count x; $[0N=b;1+last x;b]}
f -1 -4 -3
1
f 1 3 2
4
f 3 -1 1 0 4
2

优化方案：O(n)时间、无排序实现 #

存在无需排序的O(n)时间复杂度方案，核心思路是利用数组本身作为哈希表，将每个正整数放到其对应的索引位置（比如数字k应该放在索引k-1处），之后遍历数组找到第一个索引与值不匹配的位置，该位置+1就是答案；如果所有位置都匹配，答案就是数组长度+1。

Q语言实现代码 #

f_opt: {
    // 过滤非正整数，仅保留正整数
    x: x where x>0;
    n: count x;
    // 原地交换，将每个数放到对应索引位置
    i: 0;
    while[i < n;
        val: x[i];
        // 仅当当前值在有效范围且未在正确位置时交换
        if[val >=1 and val <=n and x[val-1] != val;
            // 交换x[i]与x[val-1]
            x: @[x; (i; val-1); (x[val-1]; val)];
        ] else {
            i: i+1;
        };
    ];
    // 查找第一个不匹配的位置
    res: first where not x = 1+til n;
    // 若全部匹配则返回n+1，否则返回位置+1
    $[0N=res; n+1; res+1]
}

测试验证 #

f_opt -1 -4 -3
1
f_opt 1 3 2
4
f_opt 3 -1 1 0 4
2

复杂度说明 #

• 时间复杂度：O(n)，每个元素最多被交换一次，遍历和交换操作均为线性时间。
• 空间复杂度：O(1)（若允许直接修改原数组，可省略过滤步骤进一步优化空间）。

内容的提问来源于stack exchange，提问作者Utsav