当前位置：首页 > news >正文

算法打卡力扣第88题：合并两个有序数组（easy）

news 2025/8/13 18:10:43

题目

题目链接
在这里插入图片描述

我的解答思路

首先想到的是归并排序，恰好两路归并排序算法是稳定的算法，决定套模板（3w）用空间换时间
我新开了一个数组nums3，然后之后再把nums3复制给nums1。然后因为m+n限制在200以内所以我的nums3开的210的大小

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = 0, j = 0, k = 0;int nums3[210];while (i < m && j < n) {if (nums1[i] <= nums2[j])nums3[k++] = nums1[i++];elsenums3[k++] = nums2[j++];}while (i < m)nums3[k++] = nums1[i++];while (j < n)nums3[k++] = nums2[j++];for(int i=0;i<k;i++){nums1[i]=nums3[i];}}
};

也是顺利通过了！
在这里插入图片描述

复杂度分析

时间复杂度：O（m+n）
空间复杂度：O（m+n）

另优解：从后向前的双指针法(来自gimini老师的教学)

直接在 nums1 数组上操作，但通过从末尾开始填充，完美地避免了覆盖 nums1 中尚未被比较的原始数据。
指针定义
我们需要三个指针：

p1：指向 nums1 中最后一个有效元素。初始位置为 m - 1。
p2：指向 nums2 中最后一个元素。初始位置为 n - 1。
p_merge：指向 nums1 数组的最末尾，这是我们将要填充的位置。初始位置为 m + n - 1。

Step1：初始化指针

int p1 = m-1;
int p2 = n-1;
int p_merge = m+n-1;

Step2 从后向前比较和填充

进入一个 while 循环，循环条件是 p2 >= 0。为什么是 p2？因为只要 nums2 还没合并完，我们就需要继续操作。如果 nums2 合并完了，而 nums1 还有剩余（p1 >= 0），那么这些 nums1 的元素本身就在正确的位置上，不需要移动。
在循环内部，进行比较：

情况一：p1 还在界内，并且 nums1[p1] 大于 nums2[p2]
说明当前两个数组的末尾元素中，nums1 的更大。
将这个较大的值 nums1[p1] 放入 nums1 的 p_merge 位置。

nums1[p_merge] = nums1[p1];

移动 p1 和 p_merge 指针，去比较下一个位置。

p1--;
p_merge--;

情况二：其他情况
这包含了两种子情况：

p1 还在界内，但 nums1[p1] <= nums2[p2]。

p1 已经越界了（p1 < 0），说明 nums1 的所有有效元素都已经合并完毕，现在只需要把 nums2 中剩余的元素逐个放入 nums1 的前端即可。

在这两种子情况下，我们都应该将 nums2[p2] 的值放入 nums1[p_merge] 的位置。

nums1[p_merge] = nums2[p2];

移动 p2 和 p_merge 指针。

p2--;
p_merge--;

Step3 循环结束

当 p2 变为 -1 时，循环终止。此时，所有 nums2 中的元素都已经被正确地合并到了 nums1 中，整个 nums1 数组 (0 到 m+n-1) 就变得有序了。

完整代码实现

class Solution {
public:/*** @brief 使用从后向前的双指针法合并两个有序数组* @param nums1 目标数组，长度为 m+n，后 n 个元素为0* @param m nums1 中的有效元素个数* @param nums2 要合并的数组，长度为 n* @param n nums2 中的元素个数*/void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 初始化指针：p1 指向 nums1 的有效元素末尾int p1 = m - 1;// p2 指向 nums2 的末尾int p2 = n - 1;// p_merge 指向 nums1 的最末尾，用于放置最终结果int p_merge = m + n - 1;// 只要 nums2 还没有被完全合并，就继续循环while (p2 >= 0) {// 如果 p1 还在界内，并且 p1 指向的元素大于 p2 指向的元素if (p1 >= 0 && nums1[p1] > nums2[p2]) {// 将 nums1[p1] 这个较大的值放到 nums1 的末尾nums1[p_merge] = nums1[p1];// 移动 p1 指针，向前一位p1--;} else {// 发生以下两种情况之一：// 1. p1 越界了 (m=0 的情况)// 2. nums2[p2] 的值大于或等于 nums1[p1] 的值// 无论哪种情况，都应将 nums2[p2] 的值放到 nums1 的当前合并位置nums1[p_merge] = nums2[p2];// 移动 p2 指针，向前一位p2--;}// 每次放置一个元素后，合并指针 p_merge 都需要向前移动p_merge--;}// 当 p2 < 0 时，循环结束。// 无需处理 p1 > 0 的情况，因为那些元素已经在正确的位置上了。}
};