内容简介:题干:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。说明:
合并两个有序数组(Merge-Sorted-Array)
题干:
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
来源:力扣(LeetCode)
这是一题关于数组的题目。目前为止讲解数组、字符串相关的题目都会引入一个解题思路: 双指针思路 。其实就是想让小伙伴们培养一个习惯:面对数组、字符串类型的题目先用 双指针思路 来捣腾捣腾。
当然这题也是引用这个思路来解题,只不过这时候的 双指针 不在指向一个数组,而是分别指向数组 num1 和 num2 。
解题思路
简单粗暴的方式就是将 num1 和 num2 直接合并,再重新排序,当然不建议这么做啦。
我们仔细审一下题:题目告诉我们 num1 和 num2 是有序的,并且是从小到大 排序 的。那我们是不是可以从左到右依次比较 num1 和 num2 中的元素值,并将 较小的值minV 逐一存储到一个新的数组 num3 中。
但是题目有一个限制:需要将 num2 直接合并到 num1 中。这时候我们发现用从左到右的方式遍历,并将 minV 插入到 num1 中势必会产生挪动 num1 元素的操作,例如:需要在 num1 索引为 2 的位置插入 minV ,那么需要将原本 索引为 2 的元素以及之后的元素都向后挪一位,空出索引为 2 的位置 。成本有点大,并且也不好实现。
那么如何解决上面的问题呢?其实换成从右向左遍历就行啦。我们知道 num1 现在的长度为 m ,当前最大索引记为 i , num2 的长度为 n ,当前最大索引记为 j ,合并之后 num1 的长度应该是 m + n ,最大索引记为 max 。我们比较 num1[i] 与 num2[j] 的大小,如果 num1[i] 大于 num2[j] ,那么 num1[max] = num1[i],max 向左移动一位,i 向左移动一位 ,反之 num1[max] = num2[j],max 向左移动一位,j 向左移动一位 。重复上面的操作,具体流程以及一些边界问题,查看下面的流程图:
代码实现
func merge(nums1 []int, m int, nums2 []int, n int) { // max 指向 nums1 与 nums2 合并之后的最后一个元素 max := m + n - 1 // 指向 num1 最后一个元素 i := m - 1 // 指向 num2 最后一个元素 j := n -1 for i >= 0 && j >= 0 { // 从右向左比较值的大小 if nums1[i] > nums2[j] { nums1[max] = nums1[i] // i 向左移动 i-- } else { nums1[max] = nums2[j] // j 向左移动 j-- } // max 向左移动 max -- } // 如果 i 越界了,将 nums2 剩余的元素赋值到 num1 的 [0,m] 之间 for j >= 0 { nums1[max] = nums2[j] max-- j-- } // 如果 j 越界了,其实下面这个循环可以省略。 for i >= 0 { nums1[max] = nums1[i] max-- i-- } }
总结
欢迎关注我们的微信公众号,每天学习 Go 知识
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 菜鸡的算法修炼:数组(旋转数组的最小数字)
- 算法-计算小数组在大数组中的索引
- 数组查询算法(JavaScript)
- JavaScript数组-排序算法
- 算法面试:数组编码面试问题
- 数据结构与算法: 数组
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
智能Web算法(第2版)
【英】Douglas G. McIlwraith(道格拉斯 G. 麦基尔雷思)、【美】Haralambos Marmanis(哈若拉玛 玛若曼尼斯)、【美】Dmitry Babenko(德米特里•巴邦科) / 达观数据、陈运文 等 / 电子工业出版社 / 2017-7 / 69.00
机器学习一直是人工智能研究领域的重要方向,而在大数据时代,来自Web 的数据采集、挖掘、应用技术又越来越受到瞩目,并创造着巨大的价值。本书是有关Web数据挖掘和机器学习技术的一本知名的著作,第2 版进一步加入了本领域最新的研究内容和应用案例,介绍了统计学、结构建模、推荐系统、数据分类、点击预测、深度学习、效果评估、数据采集等众多方面的内容。《智能Web算法(第2版)》内容翔实、案例生动,有很高的阅......一起来看看 《智能Web算法(第2版)》 这本书的介绍吧!