CONTEXT
let ns
be an unsorted array of unique integers of arbitrary length, return the smallest missing positive number of that array. for example
ns = {-1, -3, -2} -> 1
ns = {1, 2, 3, 4, 5, 6, 7, 8, 9} -> 10
ns = {-1, 5, 1} -> 2
I saw this on an APL youtube video and decided to give it a try myself, my solution is
smallestMissingPositive ← {⌊/(⍳⌈/⍪(1∘+)⌈/⍵)~⍵}
explanation:
- the
⍳⌈/⍪(1∘+)⌈/
part is is just all positive number up to N+1 where N is the greatest number in⍵
. Using a fork to concatenate ⍳⌈/ (a list of positive integers up to the greatest number in⍵
) with (1∘+)⌈/ (the greatest number in⍵
plus 1) ~⍵
just takes the difference of the previous point to the original list⌊/
then finally taking the minimum value on that list
so for ns = {-1, 1, 3, -2, 5}
first we generate {1, 2, 3, 4, 5, 6}
then take the difference of ns
from that which is {2, 4, 6}
then taking the minimum element which is 2
.
QUESTION
Is there a way to optimize my solution further?
HUNCHES
- I don't even know if my solution is correct or not (i.e. misses a corner case)
- the max-reduce
⌈/
function is used twice in⍳⌈/⍪(1∘+)⌈/
. the 3-train fork turnsfgh ⍵
into(f ⍵) g (h ⍵)
but in this particular case the pattern is(h (f ⍵)) g (h' (f ⍵))
can remove the redundancy inf
?
Aucun commentaire:
Enregistrer un commentaire