回答編集履歴
1
mex5の追加
answer
CHANGED
|
@@ -1,3 +1,8 @@
|
|
|
1
|
+
計算量・考え方はmex2と同じですが、オマケでnumpyを使ったmex5を作ってみました。
|
|
2
|
+
速度はmex2より2割くらいマシですが、mex1, 3, 4より遅いですね。
|
|
3
|
+
|
|
4
|
+
---
|
|
5
|
+
|
|
1
6
|
ディスカッションのスタート用に何パタンか書いてみました。
|
|
2
7
|
|
|
3
8
|
ソートして二分探索するとワースト実行時間を改善できるかと思いましたが、
|
|
@@ -10,6 +15,7 @@
|
|
|
10
15
|
|
|
11
16
|
from timeit import timeit
|
|
12
17
|
from random import choices, shuffle
|
|
18
|
+
import numpy as np
|
|
13
19
|
|
|
14
20
|
def mex1(inp):
|
|
15
21
|
check = set(inp) # set化しないと遅い
|
|
@@ -40,8 +46,16 @@
|
|
|
40
46
|
# mex1を書換えただけ
|
|
41
47
|
def mex4(inp):
|
|
42
48
|
check = set(inp)
|
|
43
|
-
return next(i for i in range(1, len(check)+
|
|
49
|
+
return next(i for i in range(1, len(check)+2) if i not in check)
|
|
44
50
|
|
|
51
|
+
# mex2と同じ考え方をnumpyブール型で
|
|
52
|
+
def mex5(inp):
|
|
53
|
+
arr = np.array(inp)
|
|
54
|
+
sieve = np.zeros(len(inp)+10, dtype=bool)
|
|
55
|
+
sieve[0] = True
|
|
56
|
+
sieve[np.where(arr > len(inp), 0, arr)] = True
|
|
57
|
+
return np.where(sieve == False)[0][0]
|
|
58
|
+
|
|
45
59
|
size = 10**6
|
|
46
60
|
ans = {987654, 525252} # この数字以外のリストを生成
|
|
47
61
|
arr = [i for i in range(1, size) if i not in ans]
|