Pythonで隣接要素の条件付きスワップにより配列をソートできるか判定する方法

問題の概要

0からn-1までの範囲に含まれる要素で構成された、順序がバラバラの数値配列numsがあるとします。この配列に対しては、「隣接する2つの要素の絶対差が1である場合に限り」隣接要素同士を入れ替える(スワップする)ことができます。必要な回数だけスワップを繰り返せるとして、このnumsを昇順にソートできるかどうかを判定するのが目的です。

例えば、入力が nums = [1, 0, 3, 2, 5, 4] の場合、出力はTrueになります。これは、ペア (1, 0)、(3, 2)、(5, 4) をそれぞれスワップすることで、[0, 1, 2, 3, 4, 5] というソート済みの配列を作れるためです。

解法のアプローチ

この問題は、配列を左から順に走査しながら、以下の手順で判定できます。

• i を 0 から numsのサイズ - 2 まで繰り返します。
• もし nums[i] > nums[i+1](逆転が発生している)ならば:
  • nums[i] - nums[i+1] がちょうど1であれば、nums[i] と nums[i+1] を交換します。
  • それ以外の場合は、これ以上ソートできないため False を返します。

ループが最後まで完了すれば、すべての逆転を解消できたことになるので True を返します。

なぜこの方法で正しく判定できるのかというと、絶対差が1の隣接要素しか交換できないため、各要素は「自分の値 ± 1」との位置関係しか変更できません。左から貪欲に(greedyに)逆転を解消していき、解消できない逆転が見つかった時点でFalseとなる、シンプルかつ確実な仕組みです。

実装例

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

def solve(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            if nums[i] - nums[i+1] == 1:
                nums[i], nums[i+1] = nums[i+1], nums[i]
            else:
                return False
    return True

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

入力

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

出力

True

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1)(入力配列をその場で書き換える場合)です。配列を一度走査するだけで判定できるため、非常に効率的な解法と言えます。