【Python】配列内で「x + 1」も存在する要素をカウントするプログラム

問題概要

数値のリスト nums が与えられたとき、その要素 x のうち「x + 1」という値も同じ配列内に存在するものの個数を求める問題です。

例えば、nums = [4, 2, 3, 3, 7, 9] の場合、出力は 3 になります。その理由は以下の通りです。

• 2 + 1 = 3 が配列内に存在する
• 3 + 1 = 4 が配列内に存在する
• もう一つの 3 も同様に条件を満たす

これらを合わせると、条件を満たす要素は合計 3 個となります。

解法のアプローチ

この問題は、各要素の出現回数を記録しておき、隣接する値(i + 1)が存在するかどうかを効率的に確認することで解けます。具体的な手順は以下の通りです。

1. 答えを格納する変数 answer を 0 で初期化します。
2. c として、nums 内の各要素の出現回数(頻度)を格納した辞書(Counter)を作成します。
3. dlist として、c のすべてのキーからなるリストを作成します。
4. dlist の各要素 i について、c[i + 1] > 0(つまり i + 1 が配列内に存在する)であれば、answer に c[i] を加算します。
5. 最後に answer を返します。

重複した要素(上記の例では 3 が 2 回出現)もそれぞれカウントされるため、単純な集合ではなく頻度ベースの管理が必要になる点がポイントです。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

from collections import Counter

def solve(nums):
    answer = 0
    c = Counter(nums)
    dlist = list(c.keys())
    for i in dlist:
        if c[i + 1] > 0:
            answer += c[i]

    return answer

nums = [4, 2, 3, 3, 7, 9]
print(solve(nums))

入力

[4, 2, 3, 3, 7, 9]

出力

3

計算量について

このアルゴリズムでは、Counter の作成に O(n)、キーの走査にも最大 O(n) しかかからないため、全体の時間計算量は O(n) です。空間計算量もユニークな要素数に依存し O(n) となります。

辞書(ハッシュマップ)を利用することで、「i + 1 が存在するか」という確認を毎回 O(1) で行えるのがこの手法の強みです。もしリストに対して i + 1 in nums のように直接存在確認を行うと、各要素ごとに O(n) かかり、全体で O(n²) になってしまうため注意しましょう。