算法题面试题golang

解题思路 一、题目描述 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 nums1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 的空间大小等于 m + n。 二、解题思路 本题是一个合并有序数组的问题，我们可以使用双指针的方法来解决。 具体的思路如下： 1、定义两个指针 p1 和 p2，分别表示 nums1 和 nums2 的已排序部分的末尾位置。 2、初始化 p1 = m-1，p2 = n-1。 3、从右往左遍历 nums1，比较 nums1[p1] 和 nums2[p2] 的大小，将较大值放到 nums1 的末尾。 4、重复步骤 3，直到 p2 < 0 或者 p1 < 0。 5、如果 p2 >= 0，则将 nums2 中剩余的元素复制到 nums1 的前面。 代码实现 下面是使用上述思路编写的 Golang 代码实现： func merge(nums1 []int, m int, nums2 []int, n int) { p1 := m - 1 p2 := n - 1 p := m + n - 1 for p2 >= 0 { if p1 >= 0 && nums1[p1] > nums2[p2] { nums1[p] = nums1[p1] p1-- } else { nums1[p] = nums2[p2] p2-- } p-- } for p2 >= 0 { nums1[p] = nums2[p2] p2-- p-- } } 解题效果验证 我们可以使用一个简单的测试用例来验证上面的代码是否正确。 func main() { nums1 := []int{1, 2, 3, 0, 0, 0} m := 3 nums2 := []int{2, 5, 6} n := 3 merge(nums1, m, nums2, n) fmt.Println(nums1) } 输出结果为 [1, 2, 2, 3, 5, 6]，与预期结果相符。 思考拓展 本题是合并两个有序数组，我们也可以考虑使用归并排序的思想来解决。 具体的思路如下： 1、定义一个辅助数组 temp，用于存储合并后的数组。 2、初始化指针 i,j 和 k，分别表示 nums1，nums2 和 temp 的起始位置。 3、比较 nums1[i] 和 nums2[j] 的大小，将较小值放入 temp[k] 中，并将指针向后移动一位。 4、重复步骤 3，直到 i >= m 或者 j >= n。 5、将 nums1 剩余的元素复制到 temp 中。 6、将 temp 复制回 nums1。 此方法的时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 (以下是Golang代码版示例) func merge(nums1 []int, m int, nums2 []int, n int) { temp := make([]int, m+n) i, j, k := 0, 0, 0 for i < m && j < n { if nums1[i] <= nums2[j] { temp[k] = nums1[i] i++ } else { temp[k] = nums2[j] j++ } k++ } for i < m { temp[k] = nums1[i] i++ k++ } for j < n { temp[k] = nums2[j] j++ k++ } copy(nums1, temp) } 拓展思考验证 我们可以使用一个简单的测试用例来验证上面的代码是否正确。 func main() { nums1 := []int{1, 2, 3, 0, 0, 0} m := 3 nums2 := []int{2, 5, 6} n := 3 merge(nums1, m, nums2, n) fmt.Println(nums1) } 输出结果为 [1 2 2 3 5 6]，与预期结果相符。 结语 通过双指针的方法，我们可以高效地解决合并有序数组的问题。在实际开发中，我们可以根据具体情况选择合适的算法和数据结构，以避免不必要的计算和内存消耗。希望本文对你有所帮助，谢谢阅读！