主页 / coding / 问题 / 79557159
Accepted
Utsav
Asked: 2025-04-05 23:18:09 +0800 CST

返回第一个缺失的正整数

  • 772

这里有一个包含正值和负值的整数列表。我们需要返回第一个缺失的正整数。

例如。

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

我可以想出下面的解决方案，它可能有很大的优化空间。只是想检查是否有不使用排序逻辑的 O(n) 解决方案。如果没有，那么请采用下面的其他优化解决方案。

q)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]}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2
kdb+

2 个回答

  1. 与 Cathal 的答案的逻辑类似，但使用except代替c where not c in x，并删除条件检查：

    q)f:{(1+max x)^first(1+til count x)except x}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2

    权衡之下，当所有输入都 <0 时，速度会较慢（因为它不会提前中止），但当输入 >1 时，速度会更快。

    • 2
  2. Best Answer
    q)f:{$[all x<1;1;$[null o:first c where not(c:1+til count x)in x;1+max x;o]]}
q)f -1 -4 -3
1
q)f 1 3 2
4
q)f 3 -1 1 0 4
2
    • 1

相关问题