ALDS1_4_A: Linear Search
ひとつめの数列の中に、ふたつめの数列に含まれる要素がいくつあるかを数える
線形探索って書いてあるからソートはなし?
要素数が10000個とか500個とかだから単純に二重ループでやればいいのかな
お、こんなデータがある
ループの順番に気をつけないと
5
1 1 2 2 3
2
1 2
それくらいでずいぶん簡単に見えるけど落とし穴はないかな
AC
なかったみたい
#! /usr/local/bin/python3
# coding: utf-8
def count(s, t):
c = 0
for x in t:
for y in s:
if x == y:
c += 1
break
return c
_ = int(input())
s = [int(x) for x in input().split()]
_ = int(input())
t = [int(x) for x in input().split()]
print(count(s, t))
解説を読む
あー番兵ね
番兵を入れると定数倍の高速化が期待できるそうな
とは言ってもfor ... in ...
で書いてると番兵が置けないので
カウンタ入れてやってみよう
上のコードだと#9のテストに00.03sかかってます
番兵なしだとこう書くのかな
考えてみたら外側はfor ... in ...
でもいいんだけど
#! /usr/local/bin/python3
# coding: utf-8
def count(n, s, q, t):
c = 0
i = 0
while i < q:
j = 0
ti = t[i]
while j < n:
if s[j] == ti:
c += 1
break
j += 1
i += 1
return c
n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
print(count(n, s, q, t))
これだと00.06s
番兵ありだと
#! /usr/local/bin/python3
# coding: utf-8
def count(n, s, q, t):
c = 0
i = 0
s.append(0)
while i < q:
j = 0
s[n] = t[i]
ti = t[i]
while s[j] != ti:
j += 1
if j < n:
c += 1
i += 1
return c
n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
print(count(n, s, q, t))
00.05s
速くなったと言えば速くなったけど誤差の範囲かもしれない
もうちょっと速くなってもいい気がしたけど
なんにせよpythonでは普通にfor ... in ...
で書こう