【paizaラーニング】問題集 線形探索メニュー「指定された値の探索」を解く

Python

レベルアップ問題集「定番アルゴリズムの習得」の線形探索メニュー問題をPythonで解きました。

リスト型に対する組み込みメソッド（count(), find()など）やin演算子の使用は、アルゴリズム学習の主旨から外れるため禁じ手とします。

公式解答例はメインルーチンだけで解いているようですが、私は必要に応じて関数やクラスを利用する方針でコーディングしています。 理由は、海外のオンラインジャッジにも挑戦しており、そちらではメインルーチンがなく標準入出力も使わないためです。

CodeWarsでは関数、LeetCodeではクラス（とそのメソッド）が解答様式となっています（名前もすでについているので、考える手間が省けて良いです）。

以下、私のコードの一部をご紹介します。入力行の読み込みは、説明で特に必要なもの以外は省略します。

指定された値の探索

def myCount(l: list, k: int):
    """
    リストに含まれるキーのカウント
    l: list 対象リスト
    k: int  キー
    """
    amount = 0
    for data in l:
        if data == k:
            amount += 1
    return amount

指定された値の位置1

問題ではリストの最初を「1番目」としていますが、多くのプログラミング言語では配列の先頭インデックスを0とする仕様です。

実用的な関数としては、正直にインデックスを戻り値として、問題に合わせてメインルーチン側で調整するのが良いと思います。そうすれば他のオンラインジャッジでも使いまわせるでしょう。

関数

def myLinearSearch(l: list, k: int):
    """
    線形探索
    l: list 対象リスト
    k: int  キー
    最初に見つかったキーのインデックスを返す
    見つからなかった場合は-1を返す
    """
    p = 0
    while p < len(l):
        if l[p] == k:
            return p + 1
        p += 1
    return -1

メインルーチン側

result = myLinearSearch(a, k) + 1

これで題意は満たせます。

指定された値の位置2

一次変数を用意して、見つかったキーのインデックスを保持します。リストの最後まで探索が進んだ後、その一時変数を戻り値とします。

def myLinearSearch2(l: list, k: int):
    """
    線形探索2
    l: list 対象リスト
    k: int  キー
    最後に見つかったキーのインデックスを返す
    キーが見つからなかった場合は-1を返す
    """
    p = 0
    latest = 0
    flag = False
    while p < len(l):
        if l[p] == k:
            flag = True
            latest = p
        p += 1
    if flag:
        return latest
    else:
        return -1

FINAL問題：指定された値の位置3

戻り値をリストにして、メインルーチン側でfor文を使い、各要素に対してprint()を使えば良いでしょう。

def myLinearSearch3(l: list, k: int):
    """
    線形探索 Final
    l: list 対象リスト
    k: int  キー
    見つかったキーのインデックスのリストを返す
    キーが見つからなかった場合は空のリストを返す
    """
    p = 0
    result = []
    while p < len(l):
        if l[p] == k:
            result.append(p)
        p += 1
    return result

余談

Pythonのリストのインデックスに対してfor文を使うのがとても苦手です。よくlist index out of rangeエラーを出して失敗します。

それでは、と思い今はwhile文を使っています。これはこれでインデックスの増加をし忘れるんですけどね（なのでそこまで先に書いてから中身を書くようにしています）。