项目网站开发,湖南省建设厅易小林,男女做污视频网站,网页设计免费下载题目描述
本题是leetcode一道简单题#xff1a;合并两个有序数组#xff0c;但是对于时间和空间复杂度面试官明确给出了限制。 // 给定两个排序后的数组 A 和 B#xff0c;其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法#xff0c;将 B 合并入 A 并排序。
// 初始化…题目描述
本题是leetcode一道简单题合并两个有序数组但是对于时间和空间复杂度面试官明确给出了限制。 // 给定两个排序后的数组 A 和 B其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法将 B 合并入 A 并排序。
// 初始化 A 和 B 的元素数量分别为 m 和 n。
//
// 示例:
// 输入:
// A [1,2,3,0,0,0], m 3
// B [2,5,6], n 3
//
// 输出: [1,2,2,3,5,6]
//
// 说明:A.length n m
//
// 最低要求时间复杂度O(mn)、空间复杂度O(mn) 思路分析
第一种解法合并快排
思路最简单的办法就是将B数组添加到A数组的末尾再对A数组进行快排但是其时间复杂度和空间复杂度为均不符合要求所以PASS
第二种解法双指针
思路
1初始化定义三个指针p1,p2和p分别指向数组A的m-1B的n-1和A的mn-1的下标
2遍历过程使用p1,p2指针遍历数组A和B将较大的元素放入p下标处直到将数组B的元素全部放入数组A中
3输出结果最后输出数组A 代码实现
基于以上思路Golang的代码实现如下
func MergeSortedArrays(nums1 []int, m int, nums2 []int, n int) {p1, p2, p : m-1, n-1, mn-1//直到nums2遍历完结束for p2 0 {//从后向前遍历取两者较大值//若p1先遍历完可能会出现下标越界所以应判断p10?if p1 0 nums1[p1] nums2[p2] {nums1[p] nums1[p1]p1--} else {nums1[p] nums2[p2]p2--}p--}
}
