合并两个有序数组

题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2, 另有两个整数 m 和 n, 分别表示 nums1 和 nums2 中的元素数目.

请你合并 nums2 到 nums1 中, 使合并后的数组同样按非递减顺序排列.

注意: 最终, 合并后数组不应由函数返回, 而是存储在数组 nums1 中. 为了应对这种情况, nums1 的初始长度为 m + n, 其中前 m 个元素表示应合并的元素, 后 n 个元素为 0, 应忽略. nums2 的长度为 n.

提示:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10⁹ <= nums1[i], nums2[j] <= 10⁹

示例

输入: 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 中的元素

输入: nums1 = [1], m = 1, nums2 = [], n = 0
输出: [1]
解释: 需要合并 [1] 和 [].
合并结果是 [1] .

输入: nums1 = [0], m = 0, nums2 = [1], n = 1
输出: [1]
解释: 需要合并的数组是 [] 和 [1].
合并结果是 [1].
注意, 因为 m = 0 , 所以 nums1 中没有元素. nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中.

题解

    p1              p2   /       p1            p2     /       p1          p2      /      p1            p2      /     p1          p2
    ↓               ↓    /       ↓             ↓      /       ↓           ↓       /      ↓             ↓       /      ↓           ↓
1 2 3 0 0 0     2 5 6    /   1 2 3 0 0 6     2 5 6    /   1 2 3 0 5 6     2 5 6   /    1 2 3 3 5 6     2 5 6   /    1 2 2 3 5 6     2 5 6
          ↑              /           ↑                /         ↑                 /        ↑                   /      ↑
         tail            /          tail              /        tail               /       tail                 /     tail

JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  let p1 = m - 1
  let p2 = n - 1
  let tail = m + n - 1

  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] > nums2[p2]) {
      nums1[tail] = nums1[p1]
      p1--
    } else {
      nums1[tail] = nums2[p2]
      p2--
    }
    tail--
  }

  while (p2 >= 0) {
    nums1[tail] = nums2[p2]
    p2--
    tail--
  }
}

Rust

pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
    let (mut p1, mut p2, mut tail, mut curr) = (m - 1, n - 1, m + n - 1, 0);

    while p1 >= 0 || p2 >= 0 {
        if p1 == -1 {
            curr = nums2[p2 as usize];
            p2 -= 1;
        } else if p2 == -1 {
            curr = nums1[p1 as usize];
            p1 -= 1;
        } else if nums1[p1 as usize] > nums2[p2 as usize] {
            curr = nums1[p1 as usize];
            p1 -= 1;
        } else {
            curr = nums2[p2 as usize];
            p2 -= 1;
        }

        nums1[tail as usize] = curr;
        tail -= 1;
    }
}

复杂度分析

• 时间复杂度: O(m + n), 指针移动单调递减, 最多移动 m + n 次, 因此时间复杂度为 O(m + n).
• 空间复杂度: O(1), 直接对数组原地修改, 不需要额外空间.