【专知-关关的刷题日记16】Leetcode 88. 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 initialized in nums1 and nums2 are m and n respectively.

题目的意思是给定两个排好序的数组,要求将这两个数组合并成一个排好序的数组。

方法

思路:因为题目中给定的两个数组是排好序的,所以想到用归并的方法同时从头至尾遍历两个数组,每次将较小的元素放到一个新的数组中,但是这样需要额外开辟新的空间。题目中说nums1的空间是足够大的,所以最好是在原来的nums1上直接操作,因此想到从后往前同时遍历两个数组,后面的元素也挤不到前面的元素,就可以实现不需要额外开辟空间,时间复杂度为O(n)的算法了。写程序的过程中注意当nums1到头的时候,需要把nums2剩下的部分都直接搬到nums1的前面,否则算法功能还没执行完,程序就直接退出了。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i,j,k;
        for(i=m-1,j=n-1,k=m+n-1;i>=0 && j>=0 ;k--)
        {
            if(nums1[i]>nums2[j])
            {
                nums1[k]=nums1[i--];
            }                
            else
            {
                nums1[k]=nums2[j--];
            }              
        }
        while(j >= 0) 
        {
            nums1[j] = nums2[j];
            j--; 
        }
    }
};

站在更高的山上,才能看到更远的风景,加油!

仰望星空,脚踏实地,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-10-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coding...

swift3.0 基础练习-构造对象并按要求进行排序(struct)

struct练手 构造10个学生(要求有学生的姓名、数学成绩、英语成绩),按照学生英语和数学平均分的成绩从小到大输出学生的姓名、数学成绩、英语成绩及平均分 ...

663
来自专栏专知

【 关关的刷题日记51】 Leetcode 67. Add Binary

关关的刷题日记 52 – Leetcode 125. Valid Palindrome 题目 Given a string, determine if it i...

3313
来自专栏程序员互动联盟

【面试宝典】final 关键字

面试官:你刚毕业? 小白:还没有,大四学校没有课,就想着出来找实习单位多学习学习。 面试官:很好嘛年轻人,早点出来锻炼确实是快速提高自己的一个好方法,那咱们就简...

3393
来自专栏coding for love

JS进阶系列

在JS入门难点解析系列中,我们对JS的一些重要概念,比如:作用域,作用域链,原型,原型链,继承,活动对象,this,执行环境,变量声明,函数声明等进行了详细的分...

831
来自专栏懒人开发

(2.5)James Stewart Calculus 5th Edition: Continuity

如果在一个区间中,不包括a, 则在 a点不连续(f is discontinuous at a)

1074
来自专栏玄魂工作室

如何学python 第十七课 类-面向对象的概念

欢迎回来。今天要说的东西将会改变我们写程序的方式。今天我们介绍‘类’(class)。 概述 什么叫‘类’?类,类型。变量类型。从日常生活的感觉来说,‘类’其实...

2724
来自专栏小樱的经验随笔

查找第k小的元素(O(n)递归解法)

今天分享一个小技巧,虽然是小技巧但是还是很有价值的,曾经是微软的面试题。题目是这样的,一个无序的数组让你找出第k小的元素,我当时看到这道题的时候也像很多人一样都...

3005
来自专栏CodingToDie

Python学习(八):类和对象 以另一种思维看待世界

第8 章 类和对象 以另一种思维看待世界 对世界万物的状态与行为进行归纳与分类,以此分析个体与个体间的相互作用与影响方法。 Table of Contents ...

3747
来自专栏专知

【 关关的刷题日记48】Leetcode 58. Length of Last Word

关关的刷题日记48 – Leetcode 58. Length of Last Word 题目 Given a string s consists of upp...

2604
来自专栏机器学习入门

挑战程序竞赛系列(74):4.3强连通分量分解(1)

挑战程序竞赛系列(74):4.3强连通分量分解(1) 传送门:POJ 2186: Popular Cows 题意: 每头牛都想成为牛群中的红人。给定N头牛的牛...

2228

扫码关注云+社区

领取腾讯云代金券