回答編集履歴
1
mex5の追加
test
CHANGED
@@ -1,3 +1,13 @@
|
|
1
|
+
計算量・考え方はmex2と同じですが、オマケでnumpyを使ったmex5を作ってみました。
|
2
|
+
|
3
|
+
速度はmex2より2割くらいマシですが、mex1, 3, 4より遅いですね。
|
4
|
+
|
5
|
+
|
6
|
+
|
7
|
+
---
|
8
|
+
|
9
|
+
|
10
|
+
|
1
11
|
ディスカッションのスタート用に何パタンか書いてみました。
|
2
12
|
|
3
13
|
|
@@ -21,6 +31,8 @@
|
|
21
31
|
from timeit import timeit
|
22
32
|
|
23
33
|
from random import choices, shuffle
|
34
|
+
|
35
|
+
import numpy as np
|
24
36
|
|
25
37
|
|
26
38
|
|
@@ -82,7 +94,23 @@
|
|
82
94
|
|
83
95
|
check = set(inp)
|
84
96
|
|
85
|
-
return next(i for i in range(1, len(check)+
|
97
|
+
return next(i for i in range(1, len(check)+2) if i not in check)
|
98
|
+
|
99
|
+
|
100
|
+
|
101
|
+
# mex2と同じ考え方をnumpyブール型で
|
102
|
+
|
103
|
+
def mex5(inp):
|
104
|
+
|
105
|
+
arr = np.array(inp)
|
106
|
+
|
107
|
+
sieve = np.zeros(len(inp)+10, dtype=bool)
|
108
|
+
|
109
|
+
sieve[0] = True
|
110
|
+
|
111
|
+
sieve[np.where(arr > len(inp), 0, arr)] = True
|
112
|
+
|
113
|
+
return np.where(sieve == False)[0][0]
|
86
114
|
|
87
115
|
|
88
116
|
|