👯‍♂️

[leetCode] Top Interview 150: Merge Sorted Array

2024/01/12に公開

Java

LeetCode

tech

解いたけど書いてなかった。

リンク

概要

ふたつの配列nums1とnums2が与えられる（サイズはそれぞれm+n、n）
- 2つの配列は小さい順にソートされている
nums1にnums2を マージ（合成） し、小さい順にソートする
- マージされるため、nums1の後ろにはn個の0が挿入してある
値を返す必要はない（最終的なnums1の中身を見て判断されるので）

解法

先に参考にした解法を共有。

問題の意図を明らかにするため、まずは簡単な解法から考えます。
まずは普通に配列をマージし、そのあとでソートする方法。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m;
	
	// nums1 に nums2 の要素を追加
        for (int j = 0; j < n; j++) {
            nums1[i] = nums2[j];
            i++;
        }
	
	// ソート
        Arrays.sort(nums1);
    }
}

とてもシンプル。
これでもいいけど、現状は時間計算量が $O((M+N) \log (M+N))$ となっています^[1]。
そこで、もう少し軽量なアルゴリズムを考えてみます。

ポインタを使ったマージソート

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;   // num1 のポインタ
        int p2 = n - 1;   // num2 のポインタ

        // 後ろから捜査
        for(int i = m + n - 1; i >= 0; i--) {
            if(p2 < 0) break;   // すべての値を入れ終わったので終了する
            if(p1 >= 0 && nums1[p1] >= nums2[p2]) {
                nums1[i] = nums1[p1];
                p1--;
            } else {
                nums1[i] = nums2[p2];
                p2--;
            }
        }
    }
}

nums1の後ろから、各配列の大きい要素を比較して並べていく処理です。
前提として、ふたつの配列は最初から小さい順にソートされていることに注意してください。

nums1が「値を持つ配列＋答えを入れる配列」の二つの性質を持っているので少し混乱しがちですが、これはポインタごとに分けて考えればわかりやすいかと思います。

i: nums1の「答えを入れていく部分」を指すポインタ
p1: nums1の「持っている値を参照している部分」を指すポインタ

脚注

Arrays.sort()の計算量は $O(N \log N)$ です（参照） ↩︎

リンク

概要

解法

ポインタを使ったマージソート

Discussion