首页 > itarticle > l83_merge_sorted_array

l83_merge_sorted_array

admin 11月 13, 2020 0

题目描述

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

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. 
The number of elements initialized in nums1 and nums2 are m and n respectively.

解题思路

nums1有足够的空间可以容纳2个数组的数据，故解题思路前提是不额外申请空间。
遍历nums2数据对nums1进行插入排序。

Go实现

package main

import "fmt"

func (nums1 []int, m int, nums2 []int, n int)  {
    if m == 0 {
        for k:=0;k<n;k++  {
            nums1[k] = nums2[k]
        }
    }

    if n == 0 {
        return
    }

    j:=0

    for j<n  {
        i:=0
        for i<m && nums1[i]<nums2[j]  {
            i++
        }

        if i>=m {
            nums1[i] = nums2[j]
            j++
        }else {
            t := nums1[i]
            nums1[i] = nums2[j]
            for i<m  {
                t1 :=nums1[i+1]
                nums1[i+1] = t
                t = t1
                i++
            }
            j++
        }
        m +=1
    }
}

func main()  {
    nums1 := make([]int,10)
    
    nums1[0] = 1
    nums1[1] = 0

    nums2 :=[]int{2}
    m := 1
    n := 1
    merge(nums1, m, nums2, n)
    fmt.Println(nums1[0:m+n])
}