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

给定两个有序整数数组 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)
}

原文地址:https://www.cnblogs.com/TimLiuDream/p/10084035.html

时间: 12-07

合并两个有序数组的golang实现的相关文章

合并两个有序数组

思路: 跟替换字符串中的空格一样,都是从后往前遍历.因为从前往后遍历的话,元素需要移动的次数较多. 示意图: 代码: /****************************************** 两个有序数组的合并 by Rowandjj 2014/7/16 ******************************************/ #include<iostream> using namespace std; #define MAX 1024 //合并有序数组a与有序数

合并两个有序数组为一个新的有序数组

题目:有两个有序数组a,b,现须要将其合并成一个新的有序数组. 简单的思路就是先放到一个新的数组中,再排序.可是这种没体现不论什么算法,这里考的不是高速排序等排序算法.关键应该是怎样利用有序已知这个条件.能够这样想.如果两个源数组的长度不一样,那么如果当中短的数组用完了,即所有放入到新数组中去了,那么长数组中剩下的那一段就能够直接拿来放入到新数组中去了. public class MergeTwoSortedArrays { public static int[] merge(int[] a,

高效合并两个有序数组(Merge Sorted Array)

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.The number of elements initi

算法 - 合并两个有序数组成一个有序数组

最近看到一个算法题目,觉得很有意义,就自己查资料,摸索着自己实现了代码,特记录一下. 题目:有两个数组a[]和b[],将它们合并成数组c[],需要c[]也是有序数组. 有两种实现思路: 1. 定义一个新数组,长度为两个数组长度之和,将两个数组都copy到新数组,然后排序. 2. 给两个数组分别定义一个下标,最大长度是数组长度减一,按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度时退出循环,此时较短数组已经全部放入新数组,较长数组还

合并两个有序数组(未整理)

#include "stdafx.h" #include <stdio.h> #include <windows.h> int _tmain(int argc, _TCHAR* argv[]) { int a[5] = {0,2,5,7,8}; int b[5] = {1,3,4,6,9}; int c[10],i,x,y,z; x=0;y=0;z=0; while(x<5&&y<5) { if(a[x]<b[y]) { c[z

算法--两个有序数组合并

两个有序数组合并 关键点:从后往前进行比较,这样保证数组A有用的部分不会因为在合并的过程中覆盖掉 第15节 有序数组合并练习题 有两个从小到大排序以后的数组A和B,其中A的末端有足够的缓冲空容纳B.请编写一个方法,将B合并入A并排序. 给定两个有序int数组A和B,A中的缓冲空用0填充,同时给定A和B的真实大小int n和int m,请返回合并后的数组. Java (javac 1.7) 代码自动补全 1 import java.util.*; 2 3 public class Merge {

MergeSortedArray,合并两个有序的数组

问题描述:You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively. 算法分析:合并两个数组,但是合并后的数组是原来的数组1,不能新建空间,假设数组1有

求两个有序数组的中位数

这是我做的第二个leetcode题目,一开始以为和第一个一样很简单,但是做的过程中才发现这个题目非常难,给人一种“刚上战场就踩上地雷挂掉了”的感觉.后来搜了一下leetcode的难度分布表(leetcode难度及面试频率)才发现,该问题是难度为5的问题,真是小看了它!网上搜了很多答案,但是鲜见简明正确的解答,唯有一种寻找第k小值的方法非常好,在此整理一下. 首先对leetcode的编译运行吐槽一下:貌似没有超时判断,而且small和large的数据集相差很小.此题一开始我采用最笨的方法去实现,利

每天一个小算法(2)----合并两个有序链表

每天一个小算法还是有点没时间,尽量抽出时间写一写. 今天是合并有序的链表,对单链表有点忘了,尤其是指针指来指去的,有点晕,幸好基础还算好,想了想还是能想回来. 代码使用随机数函数生成一个链表,然后对链表排序,最后合并链表并打印,删除链表的函数于算法无关紧要,所以未实现^_^. 在Linux/g++下编译运行成功. 合并思路:和合并数组有些类同,比较两个节点的元素大小然后将小的摘下来尾插到链表bList中,然后指针指向下一个节点,最后直接把非空的链表合并到bList的末尾. 1 #include

两个有序数组组成一个有序的数组

package com.hzins.suanfa; import java.util.Arrays; /** * * 两个有序数组组成一个有序的数组 * 整个循环层数为1 * 以其中一个数组做循环,注意另外一个的index是否溢出以及另外一个是否没有遍历完成 * * @author Administrator * */ public class Demo2 { /** * * 1,3,5,7 * 2,4,6,8 * @param a * @param b */ public static voi