让我们一起啃算法----合并两个有序数组

栏目: IT技术 · 发布时间: 4年前

内容简介:题干:给你两个有序整数数组 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)

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

当然这题也是引用这个思路来解题,只不过这时候的 双指针 不在指向一个数组,而是分别指向数组 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 向左移动一位 。重复上面的操作,具体流程以及一些边界问题,查看下面的流程图:

让我们一起啃算法----合并两个有序数组

代码实现

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--
    }
}

总结

每天进步一点点,加油!

算法教程项目,每天更新一题,点个 star 支持一下呀:

https://github.com/wx-satellite/learning-a...

欢迎关注我们的微信公众号,每天学习 Go 知识

让我们一起啃算法----合并两个有序数组

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Masterminds of Programming

Masterminds of Programming

Federico Biancuzzi、Chromatic / O'Reilly Media / 2009-03-27 / USD 39.99

Description Masterminds of Programming features exclusive interviews with the creators of several historic and highly influential programming languages. Think along with Adin D. Falkoff (APL), Jame......一起来看看 《Masterminds of Programming》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具