Find first missing positive: Difference between revisions
(→{{header|Wren}}: Now deals with single element and empty arrays.) |
|||
Line 54: | Line 54: | ||
var b = a.where { |i| i > 0 }.toList |
var b = a.where { |i| i > 0 }.toList |
||
Sort.insertion(b) |
Sort.insertion(b) |
||
if (b[0] > 1) return 1 |
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 |
if (b[i] - b[i-1] > 1) return b[i-1] + 1 |
||
i = i + 1 |
|||
} |
} |
||
return b[-1] + 1 |
return b[-1] + 1 |
||
} |
} |
||
System.print("The first missing positive integers for the following arrays are:\n") |
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] ] |
var aa = [ [ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-2], [1] ] |
||
for (a in aa) System.print("%(a) -> %(firstMissingPositive.call(a))")</lang> |
for (a in aa) System.print("%(a) -> %(firstMissingPositive.call(a))")</lang> |
||
Line 72: | Line 75: | ||
[7, 8, 9, 11, 12] -> 1 |
[7, 8, 9, 11, 12] -> 1 |
||
[1, 2, 3, 4, 5] -> 6 |
[1, 2, 3, 4, 5] -> 6 |
||
[-2] -> 1 |
|||
[1] -> 2 |
|||
</pre> |
</pre> |
Revision as of 19:34, 23 February 2021
Let given an unsorted integer array nums. The goal is find the smallest missing positive integer.
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
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], [-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 [-2] -> 1 [1] -> 2