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