Pythonでリスト内の「出現回数と値が一致する要素」を検索する方法

数値のリスト nums が与えられたとき、「リスト内での出現回数(頻度)が、その要素自身の値と一致する要素」が存在するかどうかを判定する問題を考えてみましょう。

たとえば、入力が [2, 4, 8, 10, 4, 4, 4] の場合を考えてみます。このリストでは 4 がちょうど4回出現しているため、条件を満たす要素が存在し、出力は True になります。

解決のアプローチ

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

• まず、各値の出現回数を記録するための辞書(マップ)res を作成します。
• 次に、res 内の各キーと値のペア (k, v) を順番に確認します。
• キー k(要素の値)と値 v(出現回数)が一致していたら、True を返します。
• 最後まで一致するペアが見つからなければ、False を返します。

それでは、実際の実装例を見てみましょう。

実装例(Pythonコード)

class Solution:
    def solve(self, nums):
        res = {}
        for i in nums:
            try:
                res[i] += 1
            except:
                res[i] = 1
        for k, v in res.items():
            if k == v:
                return True
        return False

ob = Solution()
print(ob.solve([2, 4, 8, 10, 4, 4, 4]))

入力

[2, 4, 8, 10, 4, 4, 4]

出力

True

コードの解説

このコードでは、まず空の辞書 res を用意し、リスト内の各要素について出現回数をカウントしています。try-except 構文を使うことで、まだ辞書に存在しないキーの場合は初期値 1 を設定し、既に存在する場合はカウントを +1 しています。

カウントが完了したら、res.items() で各ペアを取り出し、キー(要素の値)と値(出現回数)が一致するかどうかを判定します。

別の書き方: collections.Counter を使う方法

Pythonの標準ライブラリ collections.Counter を使えば、出現回数のカウント処理をより簡潔に記述できます。

from collections import Counter

def solve(nums):
    counts = Counter(nums)
    return any(k == v for k, v in counts.items())

print(solve([2, 4, 8, 10, 4, 4, 4]))  # True

any() 関数とジェネレータ式を組み合わせることで、条件を満たす要素が1つでもあれば即座に True を返す、効率的で読みやすいコードになります。

計算量

どちらの実装でも、時間計算量は O(n)(n はリストの長さ)、空間計算量も O(n) となります。リストを一度走査してカウントし、再度辞書の内容を確認するだけなので、大規模なデータに対しても効率的に動作します。