当前位置: 首页 > news >正文

域名空间网站石家庄全网seo

域名空间网站,石家庄全网seo,铲车找事做找哪些网站,日记类型 wordpress力扣88题:合并两个有序数组 题目描述 给定两个按非递减顺序排列的整数数组 nums1 和 nums2,以及它们的长度 m 和 n,要求将 nums2 合并到 nums1,使得合并后的数组仍按非递减顺序排列。 输入与输出 示例 1: 输入&am…

力扣88题:合并两个有序数组

题目描述

给定两个按非递减顺序排列的整数数组 nums1nums2,以及它们的长度 mn,要求将 nums2 合并到 nums1,使得合并后的数组仍按非递减顺序排列。

输入与输出

示例 1

输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]

示例 2

输入:nums1 = [1], m = 1nums2 = [], n = 0
输出:[1]

示例 3

输入:nums1 = [0], m = 0nums2 = [1], n = 1
输出:[1]

算法思路

1. 问题分析

题目要求我们原地合并两个数组:

  • nums1 的后半部分预留了足够的空间(大小为 m + n m + n m+n)。
  • nums1nums2 已经是有序的。

2. 双指针逆向合并

我们从两个数组的尾部开始比较,选择较大的元素放入 nums1 的末尾。具体步骤如下:

2.1 初始化指针
  • 定义指针 p1:指向 nums1 的有效元素的末尾(即索引 m − 1 m - 1 m1)。
  • 定义指针 p2:指向 nums2 的末尾(即索引 n − 1 n - 1 n1)。
  • 定义指针 p:指向 nums1 的总末尾(即索引 m + n − 1 m + n - 1 m+n1)。
2.2 比较与插入
  • 如果 nums1[p1] > nums2[p2],将 nums1[p1] 放入 nums1[p],并移动 p1p
  • 如果 nums1[p1] <= nums2[p2],将 nums2[p2] 放入 nums1[p],并移动 p2p
2.3 拷贝剩余元素
  • 如果 nums2 中还有未处理的元素,直接将它们拷贝到 nums1 的前面。
  • 如果 nums1 中还有未处理的元素,则无需额外操作。
2.4 循环终止条件
  • p1 < 0p2 < 0 时,循环结束。

代码实现

以下是修正后的完整代码:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i = nums1Size - 1; // 从 nums1 的尾部开始填充while (m > 0 || n > 0) {if (n > 0 && (m == 0 || nums1[m - 1] < nums2[n - 1])) {nums1[i--] = nums2[--n];} else {nums1[i--] = nums1[--m];}}
}

代码详解

1. 初始化指针

定义三个指针:

  • p1 = m - 1:指向 nums1 有效部分的末尾。
  • p2 = n - 1:指向 nums2 的末尾。
  • p = m + n - 1:指向 nums1 的尾部。

2. 从尾部向前合并

通过比较 nums1[p1]nums2[p2],将较大的元素放入 nums1[p],并更新指针。以下是操作逻辑:

if (n > 0 && (m == 0 || nums1[m - 1] < nums2[n - 1])) {nums1[p--] = nums2[--n];
} else {nums1[p--] = nums1[--m];
}

3. 拷贝剩余的 nums2

如果 nums2 中还有未处理的元素,直接拷贝:

while (n > 0) {nums1[p--] = nums2[--n];
}

复杂度分析

时间复杂度

  • 遍历数组时,每次比较、移动只需 O ( 1 ) O(1) O(1) 时间,总体复杂度为 O ( m + n ) O(m + n) O(m+n)

空间复杂度

  • 使用了常量级的额外空间,复杂度为 O ( 1 ) O(1) O(1)

测试用例

测试用例 1

输入

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出

[1,2,2,3,5,6]

测试用例 2

输入

nums1 = [1], m = 1
nums2 = [], n = 0

输出

[1]

测试用例 3

输入

nums1 = [0], m = 0
nums2 = [1], n = 1

输出

[1]

测试用例 4

输入

nums1 = [2,2,2,0,0,0], m = 3
nums2 = [2,2,2], n = 3

输出

[2,2,2,2,2,2]
http://www.tj-hxxt.cn/news/9225.html

相关文章:

  • 个人怎样做网站广州网站优化排名
  • 专门做旅游的视频网站semiconductor
  • 营销型网站sempk郑州网络seo
  • o2o网站建设天津seo排名收费
  • 自动提卡的网站怎么做的电商运营推广怎么做
  • 加盟培训网站建设域名地址查询
  • 网站项目开发流程图什么是网络营销策划
  • wordpress修改文章页面模板七台河网站seo
  • 世界杯网站建设产品推广平台有哪些
  • 网站建设 网站优化什么是长尾关键词举例
  • 贵金属网站建设天津网站建设技术外包
  • 免费注册网站软件站长工具外链查询
  • 新乡网站建设国外b站推广网站
  • 做网站有弹窗叫什么新出的app推广在哪找
  • 电子烟网站建设百度seo搜索引擎优化厂家
  • 网站全屏视频怎么做刘连康seo培训哪家强
  • 做视频赚钱的网站小程序怎么引流推广
  • 常用网站域名网站定制设计
  • 成全视频免费观看在线看第2季站优云seo优化
  • 电子商务网站建设的步骤百度收录提交工具
  • 用js做网站百度竞价推广收费标准
  • 石湾手机网站建设大型网站建设方案
  • 做房产网站哪个好建站小程序
  • 网站的建设适合小学生的新闻事件
  • 哪个网站有摄影作品seo相关ppt
  • 网站开发主机的选择怎么把平台推广出去
  • 国内购物网站案例分析网站免费搭建平台
  • 网站群cmsseo超级外链工具免费
  • 建设网站前期准备工作最近一周的国内新闻
  • 做微商能利用的网站有哪些问题河南省网站