Squares of a Sorted Array
整数の配列 nums が、非減少順にソートされた状態で与えられます。負の値が含まれる場合もあります。すべての値を二乗し、その二乗値を非減少順にソートした新しい配列として返してください。
関数
- numsinteger-array
- 整数のソート済み配列（負の数も可）
- 戻り値integer-array
- すべての値の平方を、非減少順に並べたもの
制約
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsは非減少順にソートされています。
例
- 入力
- nums = [-6, -2, 1, 3, 7]
- 出力
- [1, 4, 9, 36, 49]
- 説明
- 元の順序での平方数は36、4、1、9、49です。負の値-6と-2は大きな平方数になるため、並べ替えると36は末尾近くに移動します:
[1, 4, 9, 36, 49]。
- 入力
- nums = [-9, -4, -1]
- 出力
- [1, 16, 81]
- 説明
- すべての値が負なので、二乗すると逆順になります。81、16、1 は
[1, 16, 81]になります。
提出時に隠しテスト+14件
発展問題
平方化とソートには O(n log n) かかります。O(n) でできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
[-6, -2, 1, 3, 7]を手作業で二乗してください。配列のどの部分で順序が崩れますか。また、その理由は何ですか。最大の平方数は、
numsの最初の値または最後の値から必ず得られます。これら2つの値が0から最も遠いためです。両端にポインターを1つずつ置きます。2つの正方形を比較し、大きい方を結果の後ろに書き込んで、そのポインターを内側に移動します。すべての位置が埋まるまで繰り返します。
解説
二乗すると非負の値の順序は保たれますが、負の値の順序は逆になるため、二乗した値はソートされていません。もう一度ソートすればうまくいきますが、与えられた順序が無視されます。重要な事実は、最大の二乗値は常にnumsの両端のいずれかから得られるということです。両端を比較し、大きい方の二乗値を結果の末尾に置いて、内側へ進みます。
2乗してから並べ替える
考え方
各値を二乗して新しい配列を作り、それをソートします。二乗した値が負になることはなく、ソートすれば元の位置に関係なく順番に並びます。
[-6, -2, 1, 3, 7]の場合、二乗した値は[36, 4, 1, 9, 49]で、ソートすると[1, 4, 9, 36, 49]になります。
ソートの計算量はO(n log n)です。ここでは十分高速ですが、入力に順序がないものとして扱います。次の方法ではその順序を利用し、1回の走査で処理します。
アルゴリズム
nums内の各xについて、x * xを含む配列を作成します。- 数値の昇順に並べ替えます。
- それを返します。
def sortedSquares(nums):
return sorted(x * x for x in nums)両端からの2つのポインター
考え方
各要素を0からの距離の二乗と考えましょう。ソート済み配列では、0から最も遠い値は両端にあります。左端には最も小さい負の値、右端には最も大きい正の値があります。したがって、最大の二乗値は nums[left]² または nums[right]² であり、その間にある値ではありません。
left は0、right は n-1 に置いたまま、結果を最後の位置から逆順に埋めていきます。各ステップで両端の二乗値を比較し、大きい方を現在の位置に書き込み、そのポインターを内側へ移動します。ポインターの間に残る部分もソート済み配列なので、各ステップで同じことが成り立ちます。
[-6, -2, 1, 3, 7] の場合、49は36より大きいため、最後に入ります。次に36は9より大きく、9は4より大きく、4は1より大きいため、最後に1が位置0を埋めます。結果は [1, 4, 9, 36, 49] です。各値は1回ずつ配置されます。時間計算量は O(n) で、追加の配列は結果の配列だけです。
アルゴリズム
- 長さが
nの結果配列を作成します。leftを0に、rightをn-1に設定します。 posをn-1から0まで順にたどります。nums[left]²とnums[right]²を比較します。- 大きい方の二乗を
posに書き込み、そのポインターを内側へ1つ進めます。 - 結果を返します。
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
落とし穴と境界ケース
2ポインター版は短いですが、いくつかの細部でうまくいかなくなります。
- 結果を先頭から埋める。最小の二乗値は、値が0をまたぐ位置にあり、それは中央のどこかになることがあります。両端からわかるのは最大の二乗値だけです。後ろから埋めましょう。
- 二乗値や絶対値ではなく、
nums[left]とnums[right]を比較する。-6は3より小さいですが、その二乗値は大きくなります。 leftがrightに達したところで止める。両者が等しいとき、まだ配置されていない値が1つあります。結果のすべての位置をループするか、left <= rightを使いましょう。- 入力がすべて負、またはすべて正の場合。
[-9, -4, -1]では左ポインターが処理をすべて行い、[2, 5, 8]では右ポインターが処理をすべて行います。どちらの場合も、ソート済みの出力になる必要があります。 - JavaScriptとTypeScriptでは、比較関数なしの
sort()は数値をテキストとしてソートするため、[1, 4, 36, 9]は[1, 36, 4, 9]になります。(a, b) => a - bを渡しましょう。
よくある質問4
ソート済み配列の平方の時間計算量は何ですか？
2ポインター解法はO(n)時間で実行されます。各値は1回だけ二乗され、配置されます。二乗してからソートするとO(n log n)のコストがかかります。どちらも結果にO(n)のメモリを使用します。
なぜ最大の正方形は、両端のどちらかからできるのでしょうか？
二乗は、0からの距離が大きくなるほど大きくなります。ソート済み配列では、0より最も小さい値は最初にあり、0より最も大きい値は最後にあります。その間の値はどちらか一方よりも0に近いため、その二乗が最大になることはありません。
代わりに、先頭から結果を埋めていけますか？
はい。ただし、まず二分探索などを使って、値が 0 をまたぐ位置を見つける必要があります。その後、2 つのポインターがその位置から外側に向かって進みます。これは、ソート済みの 2 つのリストをマージするようなものです。負の値は右から左へ、負でない値は左から右へ読み取ります。後ろから埋めれば、最初から両端の位置がわかっているため、探索を避けられます。
ソート済み配列の二乗はマージ問題ですか？
実際にはそうです。負の値を二乗したものは1つのソート済みリスト（右から左へ読みます）になり、非負の値を二乗したものはもう1つのリストになります。それらを組み合わせるのはマージソートのマージ処理であり、そのため1回の線形パスで処理できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def sortedSquares(nums):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [-6, -2, 1, 3, 7]
期待値
[1, 4, 9, 36, 49]