Zenn
🦍

【LeetCode】88. Merge Sorted Array に挑戦！！

2024/12/17に公開
Go
LeetCode
tech

問題

2つの整数配列 nums1 と nums2（それぞれ昇順にソートされている）と、2つの整数 m および n（それぞれ nums1 と nums2 の要素数を表す）が与えられます。

nums1 と nums2 を1つの配列にマージし、昇順にソートされた配列にします。

最終的なソート済み配列は関数から返すのではなく、nums1 配列内に格納してください。このために、nums1 の長さは m + n となっています。ここで、最初の m 個の要素がマージ対象の要素を表し、残りの n 個の要素はすべて 0 に設定されており、無視されるべきです。nums2 の長さは n です。

例 1：
入力: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
出力: [1,2,2,3,5,6]
説明: マージする配列は [1,2,3] と [2,5,6] です。
マージ結果は [1,2,2,3,5,6] です。


例 2：
入力: nums1 = [1], m = 1, nums2 = [], n = 0
出力: [1]
説明: マージする配列は [1] と [] です。
マージ結果は [1] です。


例 3：
入力: nums1 = [0], m = 0, nums2 = [1], n = 1
出力: [1]
説明: マージする配列は [] と [1] です。
結果は [1] です。なお、m = 0 のため、nums1 に有効な要素はありません。0 は、マージ結果が nums1 に収まるために確保されています。

制約

・ nums1.length == m + n
・ nums2.length == n
・ 0 <= m, n <= 200
・ 1 <= m + n <= 200
・ -10^9 <= nums1[i], nums2[j] <= 10^9

実験（取っ掛かり）

マージ後の結果はどうなるかというと、、
※nums1（n1）、num2（n2）としています。


↓ マージ後（昇順）

それでは愚直に、それぞれの配列の頭から見ていきましょう。
n1[0]は1で、n2[0]は2で、2の方が大きいからn1[0]の隣に配置する。。その次は。。
何かうまくいきそうにありません。
とりあえず、n2をごそっと後ろに入れてみましょうか。
（何が取っ掛かりになるかわからないので、とりあえずいろいろやってみる。）

後ろに追加後のn1と求めたい結果を見比べてみましょう。
結構近いですね。
ここからわかることは、n1とn2の最大値は6ということ。

そもそも昇順にマージするので、一番右側に最大値がくればいい。
そして、n1の右側の3つの空間を利用できそうですね。
つまり、

n1とn2を比べて、大きい数をn1の右側から配置すればいい。

ということになります。

解法（思考プロセス）

方針：(1) n1とn2を比べて、大きい数をn1の右側から配置する
　　　(2) n1の右側の空間を利用する

n1とn2は昇順にソートされているので、それぞれの右側はそれぞれの最大値ということになります。
アルゴリズムはこのようになります。

  1. どちらの数が大きいか？
  2. 大きい方をPが指すところへ格納する
  3. 大きい数が入っていた配列の比べる位置を左側にずらす（今回はn2）
  4. Pを左側にずらす

次の比較

実装に入る前に、それぞれの位置を指し示すポインターを定義しておきましょう。

  • p: 大小比較した結果の大きい数（等しい数）を格納する位置を指すポインター
  • p1: n1の比較する位置を指すポインター
  • p2: n2の比較する位置を指すポインター

ちなみに、

p1の位置はn1は要素がm個あるので ⇒ (m-1)
p2の位置はn2は要素がn個あるので ⇒ (n-1)
pの位置はn1とn2の要素の合計(m+n)個あるので ⇒ (m+n-1)

となります。

解法（実装）

package main

import "fmt"

func merge(nums1 []int, m int, nums2 []int, n int) {
	p1 := m - 1
	p2 := n - 1
	p := m + n - 1

	// nums1 と nums2 を後ろから前に向かってマージ
	// p1, p2を左にずらしていくので、配列のインデックスの終わりは0。マイナスはあり得ない。
	for p1 >= 0 && p2 >= 0 {

		// nums1とnums2を比べる（アルゴリズム1）
		if nums1[p1] > nums2[p2] {

			// 大きい方をnums1のpの位置に追加する（アルゴリズム2）
			nums1[p] = nums1[p1]

			// 左にずらす（アルゴリズム3）
			p1--
		} else {
			// nums2のほうが大きい場合 ／ 等しい場合、にnums1のpの位置に追加する（アルゴリズム2）
			nums1[p] = nums2[p2]

			// 左にずらす（アルゴリズム3）
			p2--
		}

		// 左にずらす（アルゴリズム4）
		p--
	}

	// nums2 に残っている要素を nums1 にコピー
	for p2 >= 0 {
		nums1[p] = nums2[p2]
		p2--
		p--
	}

	fmt.Println("nums1 =", nums1)

}

func main() {

	nums1 := []int{1, 2, 3, 0, 0, 0}
	m := 3
	nums2 := []int{2, 5, 6}
	n := 3

	merge(nums1, m, nums2, n)
}

main.go 実行結果

nums1 = [1 2 2 3 5 6]

補足事項

	// nums2 に残っている要素を nums1 にコピー
	for p2 >= 0 {
		nums1[p] = nums2[p2]
		p2--
		p--
	}

上記を見落としがちになりますが、次の場合は先ほどのアルゴリズム（1～4）だけではnums2に要素が残ってしまいます。（先ほどのアルゴリズムを図を書いて再現してみてください。）

例）
nums1 = [3, 5, 0, 0]
nums2 = [1, 2]

■ アルゴリズム（1～4）操作後

※すいません。p1のポインターは-1の位置になります。

こちらはいたって簡単で、
nums2の現在値を現在の格納場所（nums[p]）に入れる。
そして、nums2の位置をずらす。
そして、格納場所をずらす。
これをnums2の左側まで繰り返す。（つまり、p2 = 0 の地点まで）

Discussion