Pythonで配列のサイズkのすべてのセグメントにキーが存在するか確認する方法

問題の概要

N個の要素を持つ配列A、探索対象の値p、そしてセグメントサイズkが与えられます。このとき、配列Aをサイズkごとのセグメントに区切った場合に、すべてのセグメントにキーpが含まれているかどうかを判定するのが目的です。

たとえば、入力が次のとおりだったとします。

• A = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
• p = 4
• k = 3

この場合、配列は [4, 6, 3]、[5, 10, 4]、[2, 8, 4]、[12, 13, 4] の4つのセグメントに分けられ、それぞれに値4が含まれているため、出力は True になります。

アルゴリズムの手順

この問題は、以下の手順に沿って解くことができます。

1. 外側のループ変数 i を 0 で初期化します。
2. i < n の間、次の処理を繰り返します。
   • 内側のループ変数 j を 0 で初期化し、j < k の間、arr[j + i] が p と一致するかどうかを順番に調べます。
   • 一致する要素が見つかったら、break で内側のループを抜けます。
   • 内側のループが終了した時点で j == k になっている場合、そのセグメントには p が存在しないため、False を返します。
   • i を k ずつ増やして、次のセグメントへ進みます。
3. ループ終了後に i == n であれば、配列がちょうどセグメント単位で処理し切れたことを意味するので、True を返します。
4. 余りの要素（最後の不完全なセグメント）が存在する場合は、j = i − k から配列の末尾まで走査し、p が存在するかどうかを確認します。
5. 最後まで見つからなければ False を、見つかれば True を返します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def key_in_segment_k(arr, p, k, n) :
    i = 0
    while i < n :
        j = 0
        while j < k :
            if arr[j + i] == p :
                break
            j += 1
        if j == k :
            return False
        i = i + k
    if i == n :
        return True
    j = i - k
    while j < n :
        if arr[j] == p :
            break
        j += 1
    if j == n :
        return False
    return True

arr = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]
p, k = 4, 3
n = len(arr)
print(key_in_segment_k(arr, p, k, n))

入力

[4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。各要素は高々一度だけ比較されるため、配列全体を線形時間で効率的に処理できます。なお、この実装は配列の長さ n がセグメントサイズ k で割り切れるケースを基本としており、余りのセグメントが発生する場合は後半の走査処理がそれに対応します。