Pythonで配列を「2倍ペア」に並べ替えられるか判定するプログラム

偶数の長さを持つ整数配列 nums が与えられたとします。この配列を並べ替えることで、すべてのインデックス i(0 ≤ i < len(nums)/2)に対して nums[2*i + 1] = 2*nums[2*i] という条件が成り立つようにできるかどうかを判定するのが、この記事のテーマです。

例えば、nums = [4, -2, 2, -4] の場合、[-2, -4, 2, 4] の順に並べ替えると各ペアが「前の要素のちょうど2倍」という関係を満たすため、答えは True になります。

解法の考え方

この問題は、各要素とその2倍の値をきちんとペアにできるかを確認することで解けます。アルゴリズムの手順は以下の通りです。

• collections.Counter を使い、配列内の各要素の出現回数を記録したマップ cnt を作成する
• 要素を絶対値の昇順でソートし、小さい方から順に処理する
• 各要素 x について、cnt[x] > cnt[2*x](2倍の値が足りない)場合は False を返す
• ペアを作れたら、cnt[2*x] から cnt[x] を差し引いて消費を記録する
• すべての要素を処理し終えたら True を返す

絶対値順にソートするのがポイントです。負の数(-2)と正の数(2)はそれぞれ -4・4 とペアになるため、絶対値の小さい要素から先に対応関係を固定しないと、正しく判定できないケースが出てきます。

Pythonでの実装例

from collections import Counter

def solve(nums):
    cnt = Counter(nums)
    for x in sorted(cnt, key=abs):
        if cnt[x] > cnt[2 * x]:
            return False
        cnt[2 * x] -= cnt[x]
    return True

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

入力例と出力例

入力:

[4, -2, 2, -4]

出力:

True

一方、nums = [6, 0, 8, 2, 1, 5] のような配列では、6 に対応する 3 が存在せず、また 5 の2倍である 10 もないため、出力は False になります。このように、ペアを組めない要素が1つでも残ると判定に失敗します。

計算量について

要素のソートがボトルネックとなるため、時間計算量は O(n log n)、出現回数を保持するための空間計算量は O(n) となります。配列の長さが偶数であることを前提に、シンプルなカウント処理だけで効率よく判定できるのがこの手法の魅力です。