[golang] 88. Merge Sorted Array

package topInterview
 
// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
// merge problem
//
// 88. Merge Sorted Array
//
// You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n,
// representing the number of elements in nums1 and nums2 respectively.
//
// Merge nums1 and nums2 into a single array sorted in non-decreasing order.
// The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To
// accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged,
// and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
//
// Example 1:
//
// Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// Output: [1,2,2,3,5,6]
// Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
// The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
// Example 2:
//
// Input: nums1 = [1], m = 1, nums2 = [], n = 0
// Output: [1]
// Explanation: The arrays we are merging are [1] and [].
// The result of the merge is [1].
// Example 3:
//
// Input: nums1 = [0], m = 0, nums2 = [1], n = 1
// Output: [1]
// Explanation: The arrays we are merging are [] and [1].
// The result of the merge is [1].
// Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
//
// Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и два целых числа m и n,
// представляющих количество элементов в nums1 и nums2 соответственно.
//
// Объедините nums1 и nums2 в один массив, отсортированный в неубывающем порядке.
// Окончательный отсортированный массив не должен возвращаться функцией, а вместо этого должен храниться внутри массива
// nums1. Чтобы учесть это, nums1 имеет длину m + n, где первые m элементов обозначают элементы, которые должны быть
// объединены, а последние n элементов устанавливаются в 0 и должны игнорироваться. nums2 имеет длину n.
func merge(nums1 []int, m int, nums2 []int, n int) {
 
    // Инициализировать переменные в которых будут индексы слайсов
    index1 := m - 1          // Индекс просматриваемого элемента в слайсе nums1
    index2 := n - 1          // Индекс просматриваемого элемента в слайсе nums2
    commonIndex := m + n - 1 // Индекс заполняемого элемента в слайсе nums1
 
    // Остановить цикл когда перебраны все элементы в слайсе nums2
    for index2 >= 0 {
        // Если еще не перебраны все элементы слайса num1
        // и текущий элемент слайса num2 больше элемента в стайсе nums1
        if index1 >= 0 && nums1[index1] > nums2[index2] {
            // Заменить крайний элемент в слайсе nums1 на текущий элемент
            // слайса nums1
            nums1[commonIndex] = nums1[index1]
            // Уменьшить индекс текущего элемента в nums1
            index1--
        } else {
            // В случае когда перебраны все элементы слайса nums1 или
            // текущий элемент слайса nums2 больше текущего элемента слайса nums1
            nums1[commonIndex] = nums2[index2]
            // Уменьшить индекс текущего элемента в nums2
            index2--
        }
        // Уменьшить индекс заполняемого элемента в nums1
        commonIndex--
    }
}

package topInterview
 
import (
    "reflect"
    "testing"
)
 
func TestMergeSortedArray(t *testing.T) {
    data := []struct {
        num1     []int
        m        int
        num2     []int
        n        int
        expected []int
    }{
        {
            num1:     []int{1, 2, 3, 0, 0, 0},
            m:        3,
            num2:     []int{2, 5, 6},
            n:        3,
            expected: []int{1, 2, 2, 3, 5, 6},
        },
        {
            num1:     []int{1},
            m:        1,
            num2:     []int{},
            n:        0,
            expected: []int{1},
        },
        {
            num1:     []int{4, 5, 6, 0, 0, 0},
            m:        3,
            num2:     []int{1, 2, 3},
            n:        3,
            expected: []int{1, 2, 3, 4, 5, 6},
        },
    }
 
    for i, datum := range data {
 
        merge(datum.num1, datum.m, datum.num2, datum.n)
 
        if !reflect.DeepEqual(datum.num1, datum.expected) {
            t.Errorf("unexpected result for test index %d expected %+v 'got %+v", i, datum.expected, datum.num1)
        }
    }
}