Pythonで配列が「美しい」かどうかを判定する方法

この記事では、ユニークな要素からなる配列 nums が与えられたときに、その配列が「美しい配列」と呼べる条件を満たしているかどうかを判定する方法を解説します。満たすべき条件は以下の2つです。

1. すべての要素が 1 から n の範囲内に収まっていること
2. 配列が昇順にソートされていないこと

たとえば、入力が nums = [2,6,1,5,3,4] の場合、出力は True になります。これは、すべての要素が 1〜6 の範囲に存在し、かつ昇順に並んでいないためです。

解法のアプローチ

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

• n := nums のサイズとする
• total := nums[0] で初期化する
• is_sorted := True で初期化する
• i を 1 から n-1 までループする
  • nums[i] が nums[i-1] と同じ場合 → False を返す(重複が存在するため)
  • nums[i] が nums[i-1] より小さい場合 → is_sorted := False に更新する
  • total := total + nums[i] で累積和を取る
• is_sorted が True のままなら False を返す
• total が 1 から n までの合計値と一致すれば True、そうでなければ False を返す

ポイント解説

1 から n までの整数の合計は、等差数列の公式 n×(n+1)/2 で求められます。配列の総和がこの値と一致し、かつ重複がなければ、すべての要素が 1〜n の範囲にちょうど 1 回ずつ現れることが数学的に保証されます。これにより、各要素を個別に範囲チェックする必要がなくなり、効率的な判定が可能になります。

実装例(Pythonコード)

def solve(nums):
    n = len(nums)

    total = nums[0]
    is_sorted = True

    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            return False

        if nums[i] < nums[i - 1]:
            is_sorted = False
        total += nums[i]

    if is_sorted:
        return False

    return total == (n * (n + 1) // 2)

nums = [2,6,1,5,3,4]
print(solve(nums))

入力

[2,6,1,5,3,4]

出力

True

まとめ

このアルゴリズムは O(n) の時間計算量で動作し、配列を一度走査するだけで判定を完了できます。重複チェック・昇順チェック・累積和による範囲チェックを組み合わせることで、「美しい配列」の条件を効率よく検証できるのが大きな特徴です。面接や競技プログラミングでも頻出のパターンなので、ぜひ覚えておきましょう。