首页 > Indexofsrc > Indexofsrc,c语言合并两个有序的数组中

Indexofsrc,c语言合并两个有序的数组中

互联网 2021-12-08 00:00:01 Tags:Indexofsrc

c语言的复杂度o1,C语言合并两个有序数组,时间复杂度为O(n), c语言合并两个有序数组 CSDNc语言合并两个有序的数组中 CSDN

合并两个有序数组(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)

这是一题关于数组的题目。目前为止讲解数组、字符串相关的题目都会引入一个解题思路: 双指针思路。其实就是想让小伙伴们培养一个习惯:面对数组、字符串类型的题目先用 双指针思路 来捣腾捣腾。

当然这题也是引用这个思路来解题,只不过这时候的 双指针 不在指向一个数组,而是分别指向数组 num1num2

解题思路

简单粗暴的方式就是将 num1num2 直接合并,再重新排序,当然不建议这么做啦。

我们仔细审一下题:题目告诉我们 num1num2 是有序的,并且是从小到大排序的。那我们是不是可以从左到右依次比较 num1num2 中的元素值,并将 较小的值minV 逐一存储到一个新的数组 num3 中。

但是题目有一个限制:需要将 num2 直接合并到 num1 中。这时候我们发现用从左到右的方式遍历,并将 minV 插入到 num1 中势必会产生挪动 num1 元素的操作,例如:需要在 num1 索引为 2 的位置插入 minV,那么需要将原本 索引为 2 的元素以及之后的元素都向后挪一位,空出索引为 2 的位置。成本有点大,并且也不好实现。

那么如何解决上面的问题呢?其实换成从右向左遍历就行啦。我们知道 num1 现在的长度为 m,当前最大索引记为 inum2 的长度为 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 向左移动一位。重复上面的操作,具体流程以及一些边界问题,查看下面的流程图:

06ea19535516b5fa915b5b97b0ea26e1.png

代码实现

func merge(nums1 []int, m int, nums2 []int, n int) {// max 指向 nums1 与 nums2 合并之后的最后一个元素max := m + n - 1// 指向 num1 最后一个元素i := m - 1// 指向 num2 最后一个元素j := n -1for 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--}} 总结

每天进步一点点,加油!

免责声明:非注明原创的信息,皆为程序自动获取自互联网,目的在于传递更多信息,不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给网站管理员发送电子邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),网站管理员将在收到邮件24小时内删除。