type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个按非递减顺序排列的整数数组
nums1 和 nums2,另有两个整数m和n,分别表示nums1 和 nums2中的元素数目。将
nums2合并到nums1中,使合并后的数组同样按非递减顺序排列。注意:
nums1的初始长度为m + n,其中前m个元素表示实际元素,后n个元素填充为0。nums2的长度为n。最终,合并后数组应存储在数组
nums1中。示例 1:

示例 2:
示例 3:
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
109(10的9次方)<= nums1[i], nums2[j] <= 109(10的9次方)
解法一:三指针“从后往前”原地合并(推荐)
nums1 的长度是 m + n,而前 m 位才是有效元素;尾部的 n 个槽位是留给合并结果的。如果从前往后塞较小元素,要不断搬移
nums1 中尚未处理的有效元素,开销大且易错。反过来,从后往前放置当前两数组的较大者到
nums1 尾部空位,既不会覆盖还未比较的有效元素,也天然利用了那块“缓冲区”。因此只需三个指针:i = m - 1指向nums1有效区的末尾;
j = n - 1指向nums2的末尾;
k = m + n - 1指向nums1的可写末尾;
每次把
max(nums1[i], nums2[j]) 写到 nums1[k],并向左收缩相应指针即可。当某一侧用完后,只可能是
nums2 还剩(把它直接拷到 nums1 前面);若 nums1 还剩,它们本就在正确位置,无需操作。复杂度
- 时间:O(m + n)(每个元素最多移动一次)
- 空间:O(1)
解法二:双指针(空间换时间)
若想从前往后合并(像“归并排序”那样写到目标数组头部),就会遇到“写回
nums1 会覆盖尚未读取的 nums1 有效元素”的问题。先把
nums1[:m] 拷贝到一个临时数组 tmp,然后用两个前向指针 p=0(指向 tmp)、q=0(指向 nums2),把较小者写回 nums1[r] 并前进。这样不需要移动大块数据,也不会覆盖尚未读到的值。复杂度
- 时间:O(m + n)
- 空间:O(m)(用来暂存
nums1[:m])
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-88-合并两个有序数组
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 84] 柱状图中最大的矩形
下一篇
[Leetcode 92] 反转链表II