Pythonでソート済み配列をマージする方法

問題の概要

2つのソート済み配列AとBが与えられたとき、それらをマージして1つのソート済み配列Cを作成することを考えます。なお、両者のサイズは異なっていても構いません。

例えば、A = [1,2,4,7]、B = [1,3,4,5,6,8] の場合、マージ後のリストCは [1,1,2,3,4,4,5,6,7,8] となります。

アルゴリズムの手順

この問題を解くには、以下の手順に従います。

1. i := 0、j := 0、end := Aの長さ − 1 を定義します
2. end >= 0 かつ A[end] が空(0)である間、end を 1 ずつ減らしていきます
3. j が Bの長さ未満である間、以下の処理を繰り返します
   • i > end かつ A[i] が空の場合:A[i] := B[j] とし、j を 1 増やします
   • A[i] > B[j] の場合:shift(A, i) を実行したうえで A[i] := B[j] とし、end と j をそれぞれ 1 増やします
   • i を 1 増やします

shiftメソッドの動作

要素を挿入するために使われるshiftメソッドは、以下のように動作します。

• num_arr と i を引数として受け取ります
• j := num_arrの長さ − 1 を設定します
• num_arr[j] が空(0)である間、j を 1 ずつ減らします
• j >= i である間、num_arr[j+1] = num_arr[j] として要素を後ろにずらし、j を 1 ずつ減らします

このように、既存の要素を1つ後ろにシフトすることで、Bの要素を正しい位置に挿入できる仕組みです。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = 0
        j = 0
        end = len(nums1)-1
        while end>=0 and not nums1[end]:
            end-=1
        while j<len(nums2) :
            if i>end and not nums1[i]:
                nums1[i] = nums2[j]
                j+=1
            elif nums1[i]>nums2[j]:
                self.shift(nums1,i)
                nums1[i] = nums2[j]
                end+=1
                j+=1
            i+=1
        return nums1
    def shift(self,num,i):
        j = len(num)-1
        while not num[j]:
            j-=1
        while j>=i:
            num[j+1] = num[j]
            j-=1
ob = Solution()
print(ob.merge([1,2,3,0,0,0],3,[2,5,6],3))

入力

[1,2,3,0,0,0]
[2,5,6]

出力

[1, 2, 2, 3, 5, 6]

まとめ

このアプローチでは、nums1の末尾に確保された余分な領域(0で埋められた部分)を活用しながら、nums2の要素を順番に適切な位置へ挿入していきます。挿入が必要な場合はshiftメソッドで既存要素を後ろにずらすため、追加の配列を作らずにその場(in-place)でマージが完結する点が特徴です。計算量は最悪でもO(m×n)程度ですが、余分なメモリを使わないシンプルな手法として覚えておくと役立ちます。