Find first missing positive: Difference between revisions
(Amended the task description as the third set example is in fact already sorted.) |
Thundergnat (talk | contribs) (→{{header|Raku}}: Add a Raku example) |
||
Line 20: | Line 20: | ||
[-6, -5, -2, -1] => None |
[-6, -5, -2, -1] => None |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
<lang perl6>say $_, " ==> ", 1 + .max max 1 for |
|||
[ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []</lang> |
|||
{{out}} |
|||
<pre>[1 2 0] ==> 3 |
|||
[3 4 -1 1] ==> 5 |
|||
[7 8 9 11 12] ==> 13 |
|||
[1 2 3 4 5] ==> 6 |
|||
[-6 -5 -2 -1] ==> 1 |
|||
[5 -5] ==> 6 |
|||
[-2] ==> 1 |
|||
[1] ==> 2 |
|||
[] ==> 1</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
Revision as of 20:44, 23 February 2021
Given an integer array nums, which may or may not be sorted, the goal is find the smallest missing positive integer.
For example:
nums = [1,2,0], [3,4,-1,1], [7,8,9,11,12]
output = 3, 2, 1
Julia
<lang julia> for array in [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-5, -2, -6, -1]]
a = sort(array) x = findfirst(i -> a[i] > -1 && a[i + 1] - a[i] > 1, 1:length(a)-1) println("$array => ", x != nothing ? a[x] + 1 : a[end] > -1 ? a[end] + 1 : "None")
end
</lang>
- Output:
[1, 2, 0] => 3 [3, 4, -1, 1] => 2 [7, 8, 9, 11, 12] => 10 [-6, -5, -2, -1] => None
Raku
<lang perl6>say $_, " ==> ", 1 + .max max 1 for [ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []</lang>
- Output:
[1 2 0] ==> 3 [3 4 -1 1] ==> 5 [7 8 9 11 12] ==> 13 [1 2 3 4 5] ==> 6 [-6 -5 -2 -1] ==> 1 [5 -5] ==> 6 [-2] ==> 1 [1] ==> 2 [] ==> 1
Ring
<lang ring> nums = [[1,2,0],[3,4,-1,1],[7,8,9,11,12]] numnr = list(3) numnr[1] = "[1,2,0]" numnr[2] = "[3,4,-1,1]" numnr[3] = "[7,8,9,11,12]"
for n = 1 to len(nums)
sortNums = sort(nums[n]) ln = len(sortNums) num = sortNums[ln] for m = 1 to num + 1 ind = find(nums[n],m) if ind < 1 see "the smallest missing positive integer for " + numnr[n] + ": " + m + nl exit ok next
next </lang>
- Output:
the smallest missing positive integer for [1,2,0]: 3 the smallest missing positive integer for [3,4,-1,1]: 2 the smallest missing positive integer for [7,8,9,11,12]: 1
Wren
<lang ecmascript>import "/sort" for Sort
var firstMissingPositive = Fn.new { |a|
var b = a.where { |i| i > 0 }.toList Sort.insertion(b) if (b.isEmpty || b[0] > 1) return 1 var i = 1 while (i < b.count) { if (b[i] - b[i-1] > 1) return b[i-1] + 1 i = i + 1 } return b[-1] + 1
}
System.print("The first missing positive integers for the following arrays are:\n") var aa = [
[ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []
] for (a in aa) System.print("%(a) -> %(firstMissingPositive.call(a))")</lang>
- Output:
The first missing positive integers for the following arrays are: [1, 2, 0] -> 3 [3, 4, -1, 1] -> 2 [7, 8, 9, 11, 12] -> 1 [1, 2, 3, 4, 5] -> 6 [-6, -5, -2, -1] -> 1 [5, -5] -> 1 [-2] -> 1 [1] -> 2 [] -> 1