合并两个有序数组

发表于 | 分类于 |
字数统计: 414 字 | 阅读时长 ≈ 2 分钟

题目描述：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 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]

方法一：逆向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1, p2 = n - 1, tail = m + n -1;
    int cur = 0;
    while(p1 >= 0 || p2 >= 0) {
      if(p1 == -1) {
        cur = nums2[p2--];
      } else if(p2 == -1) {
        cur = nums1[p1--];
      } else if(nums1[p1] > nums2[p2]) {
        cur = nums1[p1--];
      } else {
        cur = nums2[p2--];
      }
      nums1[tail--] = cur;
    }
    // 数组去重：删除有序数组中的重复项方法
  }
}

var merge = function(nums1, m, nums2, n) {
  let p1 = m - 1, p2 = n - 1, tail = m + n - 1;
  let cur = 0;
  while(p1 >= 0 || p2 >= 0) {
    if (p1 === -1) {
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }
    nums1[tail--] = cur;
  }
};

复杂度分析

  • 时间复杂度：O(m+n)
    指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)

  • 空间复杂度：O(1)
    直接对数组 nums 原地修改，不需要额外空间。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.7 MB, 在所有 Java 提交中击败了10.27%的用户