APL求最小缺失正整数的代码优化与正确性验证问询

背景 #

设ns为任意长度、元素唯一的未排序整数数组，需返回该数组中最小的缺失正整数。示例如下：

ns = {-1, -3, -2} -> 1
ns = {1, 2, 3, 4, 5, 6, 7, 8, 9} -> 10
ns = {-1, 5, 1} -> 2

我在APL相关YouTube视频中看到该问题后尝试自行实现，我的解决方案为：

smallestMissingPositive ← {⌊/(⍳⌈/⍪(1∘+)⌈/⍵)~⍵}

代码解释：

• ⍳⌈/⍪(1∘+)⌈/⍵用于生成从1到N+1的所有正整数，其中N是⍵中的最大值。通过拼接操作将⍳⌈/⍵（⍵最大值以内的正整数列表）与(1∘+)⌈/⍵（⍵最大值加1）合并。
• ~⍵用于计算上述生成列表与原数组的差集。
• ⌊/用于取差集中的最小值。

例如，对于ns = {-1, 1, 3, -2, 5}，先生成{1, 2, 3, 4, 5, 6}，再计算其与ns的差集{2, 4, 6}，最后取最小值得到2。

问题 #

能否进一步优化我的这个解决方案？

疑问 #

• 我不确定自己的解决方案是否正确（即是否存在遗漏的边界情况）；
• 在⍳⌈/⍪(1∘+)⌈/⍵中，max-reduce函数⌈/被调用了两次。此处模式为(h (f ⍵)) g (h' (f ⍵))，能否消除f的冗余计算？

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