合并两个有序数组的golang实现

栏目: Web · 发布时间: 2021-01-25

来源:cnblogs.com

简介  这篇文章主要介绍了合并两个有序数组的golang实现以及相关的经验技巧,文章约5013字,浏览量334,点赞数9,值得参考!

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:
  • 初始化 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]

由题目中我们可以知道其实就是把nums1的前m项和nums2的前n项合并,并放进nums1中

因为nums1要变动,所以我们拷贝nums1到一个临时变量中

    //把nums1复制到temp中
    temp := make([]int, m)
    copy(temp, nums1)

然后就是对比temp与nums2对应的值,比较哪个比较小,小的那个就插入nums1中

    t, j := 0, 0 //t为temp的索引,j为nums2的索引
    for i := 0; i < len(nums1); i++ {
        //比较nums2与temp对应值的大小,小的那个就放进nums1中
        if nums2[j] <= temp[t] {
            nums1[i] = nums2[j]
            j++
        } else {
            nums1[i] = temp[t]
            t++
        }
    }

但是这样写,总有一个会先用完,当用完的时候,索引++会导致

index out of range

所以要改进一下代码,整体代码:

// 本题的要求是,把nums1的前m项和nums2的前n项合并,放入nums1中。
func merge(nums1 []int, m int, nums2 []int, n int) {
    //把nums1复制到temp中
    temp := make([]int, m)
    copy(temp, nums1)

    t, j := 0, 0 //t为temp的索引,j为nums2的索引
    for i := 0; i < len(nums1); i++ {
        //当t大于temp的长度,那就是说temp全部放进去了nums1中,那剩下的就是放nums2剩余的值了
        if t >= len(temp) {
            nums1[i] = nums2[j]
            j++
            continue
        }
        //当j大于nums2的长度的时候,那就是说明nums2全部都放进去了nums1中,那剩下的就是放temp剩余的值了
        if j >= n {
            nums1[i] = temp[t]
            t++
            continue
        }
        //比较nums2与temp对应值的大小,小的那个就放进nums1中
        if nums2[j] <= temp[t] {
            nums1[i] = nums2[j]
            j++
        } else {
            nums1[i] = temp[t]
            t++
        }
    }
    fmt.Println(nums1)
}

 


以上就是本文的全部内容,希望对大家的学习有所帮助,版权归原作者或者来源机构所有,感谢作者,如果未能解决你的问题,请参考以下文章。

1.合并两个数组,并保持仍然有序。2.删除合并后数组中的重复元素

# 88. 合并两个有序数组(示例代码)

LeetCode 88 合并两个有序数组

88.合并两个有序数组(示例代码)

88. 合并两个有序数组(示例代码)