88. Merge Sorted Array
...大约 2 分钟
给你两个按 非递减顺序 排列的整数数组
nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目。请你 合并
nums2
到nums1
中,使合并后的数组同样按 非递减顺序 排列。**注意:**最终,合并后数组不应由函数返回,而是存储在数组
nums1
中。为了应对这种情况,nums1
的初始长度为m + n
,其中前m
个元素表示应合并的元素,后n
个元素为0
,应忽略。nums2
的长度为n
。示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0 输出:[1] 解释:需要合并 [1] 和 [] 。 合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1 输出:[1] 解释:需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
1. 使用辅助数组
1.1 使用 append
func merge(nums1 []int, m int, nums2 []int, n int) {
// 辅助数组
res := make([]int, 0, m+n)
p1, p2 := 0, 0
for p1 < m && p2 < n {
if nums1[p1] < nums2[p2] {
res = append(res, nums1[p1])
p1++
} else {
res = append(res, nums2[p2])
p2++
}
}
if p1 == m {
res = append(res, nums2[p2:]...)
} else {
res = append(res, nums1[p1:]...)
}
copy(nums1, res)
}
1.2 使用指针
func merge(nums1 []int, m int, nums2 []int, n int) {
// 辅助数组
res := make([]int, m+n)
p1, p2 := 0, 0
p3 := 0
for p3 < m+n {
val := 0
if p1 > m-1 {
val = nums2[p2]
p2++
} else if p2 > n-1 {
val = nums1[p1]
p1++
} else if nums1[p1] < nums2[p2] {
val = nums1[p1]
p1++
} else {
val = nums2[p2]
p2++
}
res[p3] = val
p3++
}
copy(nums1, res)
}
2. 无辅助数组
因为nums1
需要直接将结果插入nums1
中, 那么采用倒序插入的方式, 避免将原数据覆盖
func merge(nums1 []int, m int, nums2 []int, n int) {
// 辅助数组
res := make([]int, m+n)
p1, p2 := 0, 0
p3 := 0
for p3 < m+n {
val := 0
if p1 > m-1 {
val = nums2[p2]
p2++
} else if p2 > n-1 {
val = nums1[p1]
p1++
} else if nums1[p1] < nums2[p2] {
val = nums1[p1]
p1++
} else {
val = nums2[p2]
p2++
}
res[p3] = val
p3++
}
copy(nums1, res)
}
Reference
Powered by Waline v2.15.2