Pythonで指定された条件を満たすように配列の要素を並べ替えられるか判定する方法

配列 nums が与えられたとき、その要素を並べ替えることで、以下の条件を満たす配置が可能かどうかを判定する問題を考えてみましょう。

条件： すべてのインデックス i に対して、nums[2*i + 1] = 2 * nums[2*i] が成り立つこと。つまり、隣接する2つの要素からなるペアにおいて、後ろ側（奇数番目）の要素が、前側（偶数番目）の要素のちょうど2倍になっていなければなりません。

例えば、入力が nums = [8, -4, 4, -8] の場合、出力は True になります。これは、配列を [-4, -8, 4, 8] のように並べ替えると、以下のように条件を満たすためです。

• i = 0 のとき：nums[2*0 + 1] = nums[1] = -8 = 2 * (-4)
• i = 1 のとき：nums[2*1 + 1] = nums[3] = 8 = 2 * 4

解法のアプローチ

この問題は、各要素とその2倍の値をペアにできるかどうかを効率的に確認することで解けます。負の数も含まれるため、絶対値の昇順で要素を処理するのがポイントです。具体的な手順は以下の通りです。

1. nums の各要素とその出現回数を記録した頻度マップ（freq）を作成します。
2. nums を絶対値の昇順でソートし、各要素を順に処理します。
3. 現在の要素の出現回数が0であれば、すでに使用済みなのでスキップして次へ進みます。
4. 現在の要素の2倍の値（2 * item）の出現回数が0であれば、ペアを作れないため False を返します。
5. ペアが作れる場合は、両方の要素の出現回数を1ずつ減らします。
6. すべての要素を処理できたら True を返します。

絶対値でソートするのは、負の数の場合「2倍」すると絶対値が大きくなるためです。例えば -4 の2倍は -8 であり、絶対値の小さい順に処理することで、必ず「元の値 → 2倍の値」という正しい順序でペアリングを行えます。

実装例

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

from collections import defaultdict

def solve(nums):
    freq = defaultdict(int)
    for item in nums:
        freq[item] += 1
    for item in sorted(nums, key=abs):
        if freq[item] == 0:
            continue
        if freq[2 * item] == 0:
            return False
        freq[item] -= 1
        freq[2 * item] -= 1
    return True

nums = [8, -4, 4, -8]
print(solve(nums))

入力

[8, -4, 4, -8]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n log n) です。これは主にソート処理に起因するものであり、その後のループ処理自体は線形時間 O(n) で完了します。また、頻度マップを保持するために、空間計算量は O(n) 必要となります。