Description

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.

  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

将nums1、nums2两个有序数组合并到nums1一个中，nums1已分配足够空间存放元素。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func merge(nums1 []int, m int, nums2 []int, n int) {
    // from back to front
    for i := m + n - 1; i >= 0; i-- {
        n1, n2 := math.MinInt64, math.MinInt64

        if m > 0 {
            n1 = nums1[m-1]
        }
        if n > 0 {
            n2 = nums2[n-1]
        }

        // move the bigger one to the tail
        // then dec the count
        if n1 >= n2 {
            nums1[i] = n1
            m--
        } else {
            nums1[i] = n2
            n--
        }
    }
}

Similar Problem