2022/04/16

Leetcode Note: Go - Merge Sorted Array

Merge Sorted Array - LeetCode
https://leetcode.com/problems/merge-sorted-array/

Go 言語で取り組んだメモ

所感

問題文の解釈
- nums1, nums2 には、ソート済みの non-decreasing order が渡される
  - non-decreasing order は減ることのない順序・・・つまり増え続ける並びでデータが入っているということ
- m, n には nums1, nums2 の要素数が数値として渡される
- これらのデータを用いて nums1, nums2 をマージする
- 関数から配列を return するのではなく nums1 を操作することを結果とする
  - このために nums1 は m + n の長さを持ち、後ろに 0 を格納している
シンプルに考えれば nums1 のループを回して num2 の値と比較しながら nums1 を操作していけば良さそうに思える

実装準備

func merge(nums1 []int, m int, nums2 []int, n int)  {
    
}

func main() { 
    nums1 := []int{1,2,3,0,0,0}
    m := 3
    nums2 := []int{2,5,6}
    n := 3
    merge(nums1, m, nums2, n)
    fmt.Println(nums1)
}

v1

func merge(nums1 []int, m int, nums2 []int, n int)  {
    
    // merge
    for i := m; i < m + n; i++ {
        nums1[i] = nums2[i - n]
    }
    
    // bubble sort
    for i := 0; i < len(nums1) - 1; i++ {
        for j := 0; j < len(nums1) - i - 1; j++ {
            if nums1[j] > nums1[j + 1] {
                nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j]
            }
        }
    }
}

=> Runtime Error

なんか考えをうまく実装に落とし込めなかったので、シンプルに nums1 と nums2 を連結してからソートするという実装をしてみた
0 がインプットされた際に nums1[i] = nums2[i - n] の所で Runtime Error になってしまうため、エラーハンドリングが必要

v2

func merge(nums1 []int, m int, nums2 []int, n int)  {

    if m == 0 {
        for i := 0; i < m + n; i++ {
            nums1[i] = nums2[i]
        }
        return
    }
    
    if n == 0 {
        nums2 = nums1
        return
    }
    
    // merge
    for i := m; i < m + n; i++ {
        nums1[i] = nums2[i - n]
    }
    
    // bubble sort
    for i := 0; i < len(nums1) - 1; i++ {
        for j := 0; j < len(nums1) - i - 1; j++ {
            if nums1[j] > nums1[j + 1] {
                nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j]
            }
        }
    }
}

=> Runtime Error

m or n が 0 になる場合のハンドリングを実装
以下のような Input が発生すると、マージ処理の nums1[i] = nums2[i - n] で Runtime Error になってしまう
```
nums1 = [4,0,0,0,0,0]
m = 1
nums2 = [1,2,3,5,6]
n = 5
```
現状の merge 処理は m > n を前提として実装してしまっているため、 n > m の場合も想定する必要がある

v3

func merge(nums1 []int, m int, nums2 []int, n int)  {

    if m == 0 {
        for i := 0; i < m + n; i++ {
            nums1[i] = nums2[i]
        }
        return
    }
    
    if n == 0 {
        nums2 = nums1
        return
    }
    
    // merge
    if m > n {
        for i := m; i < m + n; i++ {
            nums1[i] = nums2[i - n]
        }        
    } else {
        for i := 0; i < n; i++ {
            nums1[i + m] = nums2[i]
        }
    }
    
    // bubble sort
    for i := 0; i < len(nums1) - 1; i++ {
        for j := 0; j < len(nums1) - i - 1; j++ {
            if nums1[j] > nums1[j + 1] {
                nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j]
            }
        }
    }
}

=> Runtime Error

以下の Input でマージ時に Runtime Error
- nums1[i] = nums2[i - n]
```
nums1 = [1,2,4,5,6,0]
m = 5
nums2 = [3]
n = 1
```

回答

func merge(nums1 []int, m int, nums2 []int, n int)  {

    if m == 0 {
        for i := 0; i < m + n; i++ {
            nums1[i] = nums2[i]
        }
        return
    }
    
    if n == 0 {
        nums2 = nums1
        return
    }
    
    // merge
    for i := 0; i < n; i++ {
        nums1[i + m] = nums2[i]
    }        
    
    // bubble sort
    for i := 0; i < len(nums1) - 1; i++ {
        for j := 0; j < len(nums1) - i - 1; j++ {
            if nums1[j] > nums1[j + 1] {
                nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j]
            }
        }
    }
}

試行が錯綜していたが merge 処理をシンプルに出来た
bubble sort の部分をもっと速いアルゴリズムに変更することはできそうだが、根本的には merge と同時にソートも行えるようなアプローチが速そうなので妥協