【Python】配列を等差数列に並べ替えられるかどうかを判定するプログラムの書き方

問題の概要

整数のリスト nums が与えられたとき、その要素を並べ替えることで「隣り合う2つの要素の差がすべて等しい」状態(つまり等差数列)にできるかどうかを判定するプログラムを作成します。

例えば、入力が nums = [8, 2, 6, 4] の場合、出力は True になります。これは、リストを [2, 4, 6, 8] のように並べ替えると、隣接する要素同士の差がすべて 2 で一定になるためです。

解法のアプローチ

この問題は非常にシンプルな考え方で解決できます。ポイントは「並べ替え方が自由」であることです。もし条件を満たす並べ方が存在するなら、昇順にソートした順序が必ずその一つになります。なぜなら、等差数列はソートした順序でこそ一定の間隔が現れるからです。

したがって、以下の手順で判定できます。

• N を nums の要素数とします
• N ≤ 2 の場合、2要素以下なら必ず条件を満たせるので True を返します
• リスト nums を昇順にソートします
• targetDiff(目標となる差)を nums[1] - nums[0] として求めます
• i を 2 から N-1 まで繰り返し、nums[i] - nums[i-1] が targetDiff と異なる場合は False を返します
• すべてのチェックを通過したら True を返します

実装例

以下がPythonでの実装コードです。

def solve(nums):
    N = len(nums)
    if N <= 2:
        return True
    nums.sort()
    targetDiff = nums[1] - nums[0]
    for i in range(2, N):
        if nums[i] - nums[i - 1] != targetDiff:
            return False
    return True

nums = [8, 2, 6, 4]
print(solve(nums))

入力

[8, 2, 6, 4]

出力

True

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(N log N) です。空間計算量は、インプレースでソートを行う場合は O(1)(追加領域なし)となります。要素数が多い場合でも効率的に動作する、実用的な解法といえます。