Merge Sorted Array

88. 合并两个有序数组

分析

核心思路：从后往前双指针合并

由于 nums1 后面有足够的空间，可以从后往前填充最大元素，避免频繁移动数据
使用双指针分别指向两个数组的末尾，逐步比较并将较大的数放到 nums1 的最后

初始化指针：
- i = m - 1 ：指向 nums1 有效部分的末尾
- j = n - 1 ：指向 nums2 的末尾
- k = m + n - 1 ：指向 nums1 的末尾（总长度）
双指针比较：
- 比较 nums1[i] 和 nums2[j]，将较大值放到 nums1[k]，然后指针向前移动
处理剩余元素：
- 如果 nums2 还有剩余元素，继续填充到 nums1 中（nums1 剩下的部分已经是有序的，无需处理）

复杂度分析

时间复杂度：O(m + n)
空间复杂度：O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        int i = m - 1;         // 指向 nums1 有效部分的末尾
        int j = n - 1;         // 指向 nums2 的末尾
        int k = m + n - 1;     // 指向合并后 nums1 的末尾

        // 从后往前比较，填充较大元素
        while (i >= 0 && j >= 0)
            if (nums1[i] >= nums2[j])
                nums1[k--] = nums1[i--];  // nums1 较大，放到末尾
            else
                nums1[k--] = nums2[j--];  // nums2 较大，放到末尾

        // 如果 nums2 还有剩余元素，继续填充
        while (j >= 0)
            nums1[k--] = nums2[j--];
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i, j, k = m - 1, n - 1, n + m - 1

        while i >= 0 and j >= 0:
          if nums1[i] < nums2[j]:
            nums1[k] = nums2[j]
            j -= 1
          else:
            nums1[k] = nums1[i]
            i -= 1
          k -= 1

        while j >= 0:
          nums1[k] = nums2[j]
          j -= 1
          k -= 1

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func merge(nums1 []int, m int, nums2 []int, n int)  {
  i, j, k := m - 1, n - 1, n + m - 1

  for i >= 0 && j >= 0 {
    if nums1[i] < nums2[j] {
      nums1[k] = nums2[j]
      j --
    } else {
      nums1[k] = nums1[i]
      i --
    }
    k --
  }

  for j >= 0 {
    nums1[k] = nums2[j]
    j --
    k --
  }
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


/**
 * @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 i = m - 1,
    j = n - 1,
    k = n + m - 1;

  while (i >= 0 && j >= 0) {
    if (nums1[i] < nums2[j]) {
      nums1[k--] = nums2[j--];
    } else {
      nums1[k--] = nums1[i--];
    }
  }

  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
};