Pythonで昇順ソート済みリストの二乗要素をソート順に求めるプログラム

昇順にソートされた数値のリスト nums が与えられたとき、各要素を二乗したうえで、結果をソートされた順序で返すことを考えます。

例えば、入力が nums = [-8, -3, 0, 5, 6] の場合、出力は [0, 9, 25, 36, 64] となります。負の数を含むリストでも、二乗後の値が正しく昇順に並ぶ点がポイントです。

解法のアプローチ:双方向ポインタ(Two Pointers)

単純に全要素を二乗してから再度ソートする方法もありますが、計算量は O(n log n) になります。ここでは、元のリストがすでにソートされているという性質を活かし、双方向ポインタを使った O(n) の効率的な解法を紹介します。

アイデアはシンプルです。ソート済みリストにおいて、絶対値が最も大きい要素は必ずリストの両端(先頭または末尾)に存在します。そこで、両端から中央に向かってポインタを動かしながら、絶対値の大きい方を結果リストの後ろから埋めていきます。

アルゴリズムの手順

• n := nums のサイズ
• l := 0(左端ポインタ)
• r := n - 1(右端ポインタ)
• index := n - 1(結果リストの書き込み位置)
• res := nums と同じサイズのリストを作成し、0 で初期化
• index が 0 以上である間、以下を繰り返す:
  • |nums[l]| > |nums[r]| の場合:
    • res[index] := nums[l] * nums[l]
    • l を 1 増やす
  • それ以外の場合:
    • res[index] := nums[r] * nums[r]
    • r を 1 減らす
  • index を 1 減らす
• res を返す

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(nums):
    n = len(nums)
    l = 0
    r = n - 1
    index = n - 1
    res = [0 for i in range(len(nums))]
    while index >= 0:
        if abs(nums[l]) > abs(nums[r]):
            res[index] = nums[l] * nums[l]
            l += 1
        else:
            res[index] = nums[r] * nums[r]
            r -= 1
        index -= 1

    return res

nums = [-8, -3, 0, 5, 6]
print(solve(nums))

入力

[-8, -3, 0, 5, 6]

出力

[0, 9, 25, 36, 64]

計算量について

このアルゴリズムは、各要素を一度だけ処理するため、時間計算量は O(n)、結果リスト用の追加領域が必要なため空間計算量も O(n) です。「二乗してからソートする」素朴な手法(O(n log n))と比べて、大規模なデータセットで大きな性能差が出ます。

まとめ

ソート済み配列の性質(絶対値最大の要素は両端にある)を利用することで、追加のソートなしに線形時間で二乗済みのソート済みリストを構築できます。この双方向ポインタのテクニックは、配列操作系のアルゴリズム問題で頻出のパターンなので、ぜひ覚えておきましょう。