[Leetcode 88] 合并两个有序数组

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个按非递减顺序排列的整数数组 nums1 和 nums2,另有两个整数mn,分别表示nums1nums2中的元素数目。
nums2合并到nums1中,使合并后的数组同样按非递减顺序排列。
 
注意:
nums1的初始长度为m + n,其中前m个元素表示实际元素,后n个元素填充为0nums2的长度为n
最终,合并后数组应存储在数组nums1中。
 
示例 1:
notion image
示例 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]
上一篇
[Leetcode 84] 柱状图中最大的矩形
下一篇
[Leetcode 92] 反转链表II