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--];
    }
};