go语言题解LeetCode88合并两个有序数组示例
作者:刘09k11 发布时间:2023-10-23 00:55:10
标签:go,LeetCode,合并,有序数组
题目描述
原题链接 :
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0 ,应忽略。nums2
的长度为 n
。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9 进阶:你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?
思路分析
代码超简单,从后往前看,用两个指针扫描两个数组,边比较边存数,第三个指针指向nums1的末尾存数,存储挪过来的大数。扫描指针移动条件是,该数组有小的数。
退出条件是:nums2的索引到最左边,说明数的比较和移动全部完成。需要注意的是i可能会因为nums2中的数都比较小,一直导致左超限。
AC 代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 开了三个指针,从后往前遍历,二个扫描,一个存数
int i = m-1, j = n-1, k = m+n-1;
// 循环条件:当nums2检查完,整个工作也完成了。
while (j >= 0)
{
// 注意执行顺序,先判断i >= 0,再判断数大小,否则会报索引超限错误。
if (i >= 0 && nums1[i] > nums2[j])
{
nums1[k] = nums1[i];
i--;
}
// 执行else条件:不满足if中的任意一个条件。
else
{
nums1[k] = nums2[j];
j--;
}
k--;
}
}
}
来源:https://juejin.cn/post/7172935997024370719
0
投稿
猜你喜欢
- Java8中的lambda表达式、::符号和Optional类 0. 函数式编程 函
- 介绍我们都知道函数是程序中的基本模块,代码段。那高阶函数呢?听起来很好理解吧,就是函数的高阶(级)版本。它怎么高阶了呢?我们来看下它的基本定
- 最近项目中要做一个带进度条的上传文件的功能,学习了AsyncTask,使用起来比较方便,将几个方法实现就行,另外做了一个很简单的demo,希
- 我就废话不多说了,大家还是直接看代码吧~/** * feign调用客户端 */@FeignClient(name = "user&
- 基本操作import org.apache.hadoop.conf.Configuration;import org.apache.hado
- 本文实例为大家分享了使用C#写出一个简单的记事本程序,供大家参考,具体内容如下编程语言: C# 编程环境: Visual Studio 20
- AsyncTask什么是AsyncTaskAsyncTask是一个轻量级的异步任务类,它可以在线程池中执行后台任务,然后把执行的进度和结果传
- 将10个整数按由小到大的顺序排列#include <iostream>using namespace std;int main(
- 1. 添加程序集2. 引入命名空间using System.Management;3. 方法M
- 一、开篇通过对之前Java之路的了解之后,相信初学者们都对Java有了一个比较深印象的了解了。但是事情不能总停留在理论层面,还得多多实现,才
- 废话不多说了,直接给大家贴代码了,具体代码如下所示:<?xml version="1.0" encoding=&q
- 进程同步用来实现程序并发执行时候的可再现性。一.进程同步及异步的概念1.进程同步:就是在发出一个功能调用时,在没有得到结果之前,该调用就不返
- 这篇文章主要介绍了Java方法参数传递机制原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可
- 一、线程组 /** * A thread group represents a set of threads. In addition,
- 引言第一眼看到这个题目,我相信大家都会脑子里面弹出来一个想法:这不都是 Spring 的注解么,加了这两个注解的类都会被最终封装成 Bean
- 分布式项目和传统项目的区别就是,分布式项目有多个服务,每一个服务仅仅只实现一套系统中一个或几个功能,所有的服务组合在一起才能实现系统的完整功
- 概述ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。ArrayList不是
- 动态表单的含义是不要手动定义,直接在配置文件中进行定义。1.手动进行定义<form-beans > <form-bean
- 声明:本文中资源全部收集整理于网络并无偿提供,仅可用于个人学习交流;请勿转载、售卖或商用;侵权联删!免责声明:本教程所有资源均来源于网络;仅
- 说明使用工具:brew caskbrew cask是一个用命令行管理Mac下应用的工具,提供了自动安装和卸载功能,能够自动从官网上下载并安装