線形探索の実装

AIZU ONLINE JUDGEより、線形探索に関する問題(ALDS1_4_A)をpythonで解いていきます。 onlinejudge.u-aizu.ac.jp

setクラスを用いて実装

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

temp = set(s) & set(t)
print(len(temp))

setクラスの共通部分を抽出してあげれば１行で解答は上のように算出できます。

以下では線形探索を意識して実装していきます。

線形探索を用いて実装

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

# 線形探索
def linearSearch(A: [int], key: int):
    i = 0
    A[len(A)-1] = key
    while A[i] != key:
        i += 1
    return i != n

c = 0
s.append(-1)
for i in range(len(t)):
    if linearSearch(s, t[i]):
        c += 1
print(c)

探索効率をあげるために、配列に追加する特別な要素を番兵と言います。 今回の線形探索実装でも、配列の末尾に探索対象の値をもった番兵を追加しておくことで終了条件の判定が不要にしています。

同様な問題がでたら間違いなくsetクラスを使うのがおすすめですが、アルゴリズムの知識ということで、身につけておくのもいいと思います。