リスト内で奇数回出現する要素を検索するPythonプログラム

概要

リストの中から「奇数回だけ出現する要素」を見つけたい場面は、データ処理やアルゴリズムの学習においてよくあります。Pythonでは、専用のメソッドを定義することでこの処理を簡単に実装できます。基本的な考え方は、リストを二重ループで走査して各要素の出現回数をカウントし、そのカウントが2で割り切れない場合に該当する要素を結果として返すというものです。最後まで該当する要素が見つからなければ、-1を返します。

アルゴリズムの流れ

• リストとそのサイズを引数として受け取るメソッド「odd_occurence」を定義します。

• 外側のループでリストの各要素を順番に取り出します。

• 内側のループで全要素と比較し、一致するたびにカウンター変数「count」をインクリメントします。

• ループ終了後、「count」が奇数であれば、その要素を返します。

• 奇数回出現する要素が存在しない場合は、-1を返します。

サンプルコード

def odd_occurence(my_list, list_size):

    for i in range(0, list_size):
        count = 0
        for j in range(0, list_size):
            if my_list[i] == my_list[j]:
                count += 1

        if (count % 2 != 0):
            return my_list[i]

    return -1

my_list = [34, 56, 78, 99, 23, 34, 34, 56, 78, 99, 99, 99, 99, 34, 34, 56, 56]
print("リストの内容 :")
print(my_list)
n = len(my_list)
print("リストの長さ :")
print(n)
print("奇数回出現する要素を検索するメソッドを呼び出します")
print("奇数回出現する要素は :")
print(odd_occurence(my_list, n))

実行結果

リストの内容 :
[34, 56, 78, 99, 23, 34, 34, 56, 78, 99, 99, 99, 99, 34, 34, 56, 56]
リストの長さ :
17
奇数回出現する要素を検索するメソッドを呼び出します
奇数回出現する要素は :
34

コードの解説

• リストとそのサイズをパラメータとして受け取る「odd_occurence」という名前のメソッドを定義します。

• リストのサイズを範囲として、リスト全体を反復処理します。

• 二重のネストされたループを実行し、外側と内側のループで取り出した要素が一致した場合、「count」変数をインクリメントします。

• 「count」変数が奇数の場合、リスト内の該当要素を返します。

• 整数のリストを定義し、コンソールに表示します。

• リストの長さを変数に格納します。

• 関連するパラメータを渡してメソッドを呼び出します。

• 結果をコンソールに出力します。

補足：計算量と効率的な代替手段

上記の方法はシンプルで理解しやすい反面、二重ループを使用するため計算量はO(n²)となり、リストが大きくなると処理時間が増加します。より効率的にしたい場合は、標準ライブラリのcollections.Counterを活用する方法がおすすめです。

from collections import Counter

my_list = [34, 56, 78, 99, 23, 34, 34, 56, 78, 99, 99, 99, 99, 34, 34, 56, 56]
counter = Counter(my_list)

for key, value in counter.items():
    if value % 2 != 0:
        print("奇数回出現する要素は :", key)

この方法では計算量がO(n)に抑えられ、コードも簡潔になります。用途やデータ規模に応じて、適切な実装を選択しましょう。