Find first missing positive: Difference between revisions
m
Added Easylang
m (→{{header|J}}) |
m (Added Easylang) |
||
| (10 intermediate revisions by 7 users not shown) | |||
Line 292:
{3, 4, -1, 1} -> 2
{7, 8, 9, 11, 12} -> 1</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">sets: @[[1 2 0] @[3 4 neg 1 1] [7 8 9 11 12]]
loop sets 's ->
print [
"Set:" s
"-> First missing positive integer:" first select.first 1..∞ 'x -> not? in? x s
]</syntaxhighlight>
{{out}}
<pre>Set: [1 2 0] -> First missing positive integer: 3
Set: [3 4 -1 1] -> First missing positive integer: 2
Set: [7 8 9 11 12] -> First missing positive integer: 1</pre>
=={{header|AutoHotkey}}==
Line 426 ⟶ 442:
{{out}}
<pre>⟨ 3 2 1 ⟩</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include <unordered_set>
#include <vector>
int FindFirstMissing(const std::vector<int>& r)
{
// put them into an associative container
std::unordered_set us(r.begin(), r.end());
size_t result = 0;
while (us.contains(++result)); // find the first number that isn't there
return (int)result;
}
int main()
{
std::vector<std::vector<int>> nums {{1,2,0}, {3,4,-1,1}, {7,8,9,11,12}};
std::for_each(nums.begin(), nums.end(),
[](auto z){std::cout << FindFirstMissing(z) << " "; });
}</syntaxhighlight>
{{out}}
<pre>
3 2 1 </pre>
=={{header|CLU}}==
Line 463 ⟶ 503:
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Uses the Delphi "TList" object to search the list for missing integers.
<syntaxhighlight lang="Delphi">
var List1: array [0..2] of integer =(1,2,0);
var List2: array [0..3] of integer =(3,4,-1,1);
var List3: array [0..4] of integer =(7,8,9,11,12);
function FindMissingInt(IA: array of integer): integer;
var I,Inx: integer;
var List: TList;
begin
List:=TList.Create;
try
Result:=-1;
for I:=0 to High(IA) do List.Add(Pointer(IA[I]));
for Result:=1 to High(integer) do
begin
Inx:=List.IndexOf(Pointer(Result));
if Inx<0 then exit;
end;
finally List.Free; end;
end;
function GetIntStr(IA: array of integer): string;
var I: integer;
begin
Result:='[';
for I:=0 to High(IA) do
begin
if I>0 then Result:=Result+',';
Result:=Result+Format('%3.0d',[IA[I]]);
end;
Result:=Result+']';
end;
procedure ShowMissingInts(Memo: TMemo);
var S: string;
var M: integer;
begin
S:=GetIntStr(List1);
M:=FindMissingInt(List1);
Memo.Lines.Add(S+' = '+IntToStr(M));
S:=GetIntStr(List2);
M:=FindMissingInt(List2);
Memo.Lines.Add(S+' = '+IntToStr(M));
S:=GetIntStr(List3);
M:=FindMissingInt(List3);
Memo.Lines.Add(S+' = '+IntToStr(M));
end;
</syntaxhighlight>
{{out}}
<pre>
[ 1, 2, 0] = 3
[ 3, 4, -1, 1] = 2
[ 7, 8, 9, 11, 12] = 1
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
func missing a[] .
h = 1
repeat
v = 0
for v in a[]
if h = v
break 1
.
.
until v <> h
h += 1
.
return h
.
a[][] = [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
for i to len a[][]
write missing a[i][] & " "
.
</syntaxhighlight>
{{out}}
<pre>
3 2 1
</pre>
=={{header|F_Sharp|F#}}==
Line 937 ⟶ 1,073:
drop ] is task ( [ --> n )
' [ [ 1 2 0 ]
witheach [ task echo sp ]</syntaxhighlight>
Line 951 ⟶ 1,087:
<code>uniquewith</code> is defined at [[Remove duplicate elements#Quackery]] and conveniently sorts the nest.
Then hunt for the first item which does not have the same value as its index. If they all have the same values as their indices, the missing integer is the same as the size of the processed nest.
<syntaxhighlight lang="Quackery"> [
witheach
[ dup 0 > iff
Line 960 ⟶ 1,096:
0 join
uniquewith >
dup size swap
witheach
[ i^ != if
[ drop i^
conclude ] ] ] is task ( [ --> n )
' [ [ 1 2 0 ]
witheach [ task echo sp ]</syntaxhighlight>
{{out}}
<pre>3 2 1</pre>
===Brute force===
Search for each integer. The largest the missing integer can be is one more than the number of items in the nest.
<syntaxhighlight lang="Quackery"> [ dup size
dup 1+ unrot
times
[ i^ 1+
over find
over found not if
[ dip
[ drop i^ 1+ ]
conclude ] ]
drop ] is task ( [ --> n )
' [ [ 1 2 0 ] [ 3 4 -1 1 ] [ 7 8 9 11 12 ] ]
witheach [ task echo sp ]</syntaxhighlight>
{{out}}
Line 1,056 ⟶ 1,215:
the smallest missing positive integer for []: 1</pre>
=={{header|RPL}}==
≪ 1 '''WHILE''' DUP2 POS '''REPEAT''' 1 + '''END''' SWAP DROP ≫ '<span style="color:blue">FINDF</span>' STO
{ { 1 2 0 } { 3 4 -1 1 } { 7 8 9 11 12 } } 1 ≪ <span style="color:blue">FINDF</span> ≫ DOLIST
{{out}}
<pre>
1: { 3 2 1 }
</pre>
=={{header|Ruby}}==
Line 1,062 ⟶ 1,230:
{{out}}
<pre>3, 2, 1</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">[[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], []].each {|arr|
var s = Set(arr...)
say (arr, " ==> ", 1..Inf -> first {|k| !s.has(k) })
}</syntaxhighlight>
{{out}}
<pre>[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</pre>
=={{header|True BASIC}}==
Line 1,136 ⟶ 1,321:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var firstMissingPositive = Fn.new { |a|
| |||