Merge Sorted Array
整数の配列 nums1 と nums2 が与えられます。どちらもすでに非減少順にソートされています。両方の配列のすべての値を含む単一の配列を、同じく非減少順で返してください。両方の配列に現れる値は、合計で現れる回数だけ結果に含めます。
関数
- nums1integer-array
- 最初のソート済み配列
- nums2integer-array
- 2つ目のソート済み配列
- 戻り値integer-array
- 両方の配列のすべての値を、長さが nums1.length + nums2.length の 1 つのソート済み配列にまとめたもの
制約
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1とnums2はそれぞれ非減少順にソートされています。
例
- 入力
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- 出力
- [1, 2, 3, 4, 9, 10]
- 説明
- 先頭の2つを読み取り、小さい方を残します。1、次に
nums2から2と3、続いてnums1から4と9、最後に10です。結果には6つすべての値が含まれます。
- 入力
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- 出力
- [-5, 0, 0, 0, 6, 8]
- 説明
- 0 は
nums1に 2 回、nums2に 1 回現れるため、結果には 0 が 3 つ含まれます。-5 はnums2のすべての要素より小さいため、先頭に来ます。
- 入力
- nums1 = [7]nums2 = [3]
- 出力
- [3, 7]
- 説明
- 各配列には1つの値が格納されています。3は7より小さいので、先に置きます。
提出時に隠しテスト+13件
発展問題
k 個のソート済み配列に含まれる合計 N 個の値を、O(N log k) の時間でマージできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どちらの配列もすでにソートされています。全体の結果の最小値はどこにありますか？
残っている最小の値は、常に
nums1またはnums2の先頭にあります。それぞれの先頭位置を示すために、各配列に1つずつインデックスを保持します。2つの先頭を比較し、小さい方を追加して、そのインデックスを進めます。一方の配列がなくなったら、もう一方の残りはすでに順序どおりなので、そのまま追加します。
解説
配列を結合してソートすれば正しい答えが得られますが、両方の半分がすでにソート済みであるという事実を活用できていません。全体で残っている最小の値は、必ずどちらかの配列の先頭にあります。各配列に1つずつインデックスを用意し、各ステップで先頭の値を比較して小さい方を取り出せば、1回の走査で結果を作れます。これはマージソートのマージ処理です。
連結してソート
考え方
nums1のすべての値とnums2のすべての値を1つの配列に入れてから、ソートします。結果には、各値が元の出現回数分だけ含まれ、正しい順序で並びます。
[1, 4, 9]と[2, 3, 10]の場合、結合した配列は[1, 4, 9, 2, 3, 10]となり、ソートすると[1, 2, 3, 4, 9, 10]になります。
nums1にm個の値があり、nums2にn個の値がある場合、一般的なソートの計算量はO((m + n) log(m + n))です。この方法でも動作し、今回の制約では十分高速ですが、与えられたソート済みの順序を活用していません。次の方法ではそれを活用し、logの因子をなくします。
アルゴリズム
nums1の値の後にnums2の値を続けた配列を作成します。- 数値の昇順に並べ替えます。
- それを返します。
def merge(nums1, nums2):
return sorted(nums1 + nums2)2つのポインターを、それぞれの配列に1つずつ
考え方
nums1 内のインデックス i と、nums2 内のインデックス j を保持し、どちらも 0 から始めます。i より前と j より前の値は、すでに結果に入っています。まだ使われていない最小の値は nums1[i] または nums2[j] です。各配列はソートされており、残りの値はそれより大きくなるためです。小さい方を追加し、そのインデックスを進めます。
[1, 4, 9] と [2, 3, 10] の場合: 1 は 2 より小さく、次に 2 は 4 より小さく、3 は 4 より小さく、4 は 10 より小さく、9 は 10 より小さいです。ここで nums1 を使い切ったので、nums2 の残りである [10] をそのままコピーします。結果は [1, 2, 3, 4, 9, 10] です。
各ステップで値を 1 つ書き込むため、ループは m + n 回実行されます: 時間計算量は O(m + n) です。追加のメモリは結果配列だけです。
アルゴリズム
iとjを 0 に設定し、空の結果を作成します。- 両方の配列に要素が残っている間、
nums1[i]とnums2[j]を比較します。 - 小さい方を追加し、そのインデックスを進めます。同じ値の場合は、
nums1[i]を選びます。 - 一方の配列が空になったら、もう一方に残っている要素を追加します。
- 結果を返します。
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
落とし穴と境界ケース
多くのバグは、一方の配列の要素が尽きる瞬間、または値の比較方法に現れます。
- 一方の配列を使い切った時点ですぐにループを終了し、もう一方の配列の残りを忘れてしまう。
[1, 2, 3]と[4, 5, 6]の場合、1、2、3を処理した後にループが終了し、4、5、6はまだコピーする必要があります。 iが末尾に達した後にnums1[i]を読み取る。比較する前に両方のインデックスを確認してください。- 重複を取り除いてしまう。
[0, 0]と[0]をマージすると、[0]ではなく[0, 0, 0]になります。 - JavaScript と TypeScript では、比較関数を指定せずに
sort()を使うと、数値はテキストとして並べ替えられるため、[-5, 10, 9]は[-5, 10, 9]に並べ替えられます。(a, b) => a - bを渡してください。 - Lua と R では配列のインデックスは1から始まるため、両方のインデックスを1から始め、境界条件には
<=を使います。
よくある質問4
ソート済みの2つの配列をマージする時間計算量はどれくらいですか？
2つのポインターを使うと、O(m + n) です。ここで、m と n は2つの長さです。各ステップで1つの値を配置し、同じ値を2回見ることはありません。一方、連結してソートすると、O((m + n) log(m + n)) のコストがかかります。
2つのソート済み配列をインプレースでマージするにはどうすればよいですか？
最初の配列の末尾に両方の配列の要素を格納する余地がある場合は、後ろから埋めていきます。2つの配列で残っている最大の値を比較し、大きい方を最後の空きスロットに書き込んで、左へ進みます。後ろから書き込めば、まだ配置していない最初の配列の値を上書きしないため、2つ目の配列は必要ありません。
2つのソート済み配列をマージすることは、マージソートのマージ処理と同じですか？
はい。マージソートは配列を半分に分割し、それぞれの半分をソートしてから、この2つのポインターを使うループで、ソート済みの2つの半分を結合します。同値の場合に左側の値を選ぶことで、等しい値が元の順序を保つため、マージソートは安定ソートになります。
配列を連結して sort を呼び出さないのはなぜですか？
正しい答えが得られ、実際には多くの場合高速です。しかし、入力がすでにソート済みであることを無視しており、余分なlogの計算量がかかります。面接では、2ポインターによるマージが期待される解答です。与えられた順序を活用できることを示せるからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def merge(nums1, nums2):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
期待値
[1, 2, 3, 4, 9, 10]