leetcode: 88. Merge Sorted Array
2018-08-17 本文已影响0人
唐僧取经
88. Merge Sorted Array
Description
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]
Answer
package main
import "fmt"
func merge(nums1 []int, m int, nums2 []int, n int) {
temparr := make([]int, 0, len(nums1))
for i := 0; i < n; i++ {
for j := 0; j < m+i; j++ {
if nums2[i] >= nums1[j] {
//插入最后面
if j == m+i-1 {
nums1[m+i] = nums2[i]
break
}
if nums2[i] <= nums1[j+1] {
temparr = nums1[j+1:]
nums1 = nums1[0:j+1]
nums1 = append(nums1, nums2[i])
nums1 = append(nums1, temparr...)
break
}
}
}
}
}
func merge1(nums1 []int, m int, nums2 []int, n int) {
index := len(nums1) - 1
i1 := m - 1
i2 := n - 1
for i1 >= 0 && i2 >= 0 {
n1 := nums1[i1]
n2 := nums2[i2]
if n2 > n1 {
nums1[index] = n2
i2--
} else {
nums1[index] = n1
i1--
}
index--
}
for i2 >= 0 {
nums1[index] = nums2[i2]
index--
i2--
}
}
func main() {
num := make([]int, 0, 100)
num = append(num, 1, 2, 3, 0, 0, 0)
num2 := make([]int, 0, 100)
num2 = append(num2, 2, 5, 6)
merge1(num, 3, num2, 3)
fmt.Println("num", num)
}