力扣88.合并两个有序数组【顺序表】

阿伟@t

发布于 2023-10-10 15:23:00

1540

发布于 2023-10-10 15:23:00

文章被收录于专栏：cs阿伟cs阿伟

前言：

适合学习了数据结构顺序表后做，此题虽然简单，但是必须结合画图进行分析，同时要仔细阅读题目。

题目要求：

题目分析：

思路：

但是题目中并没有让我们合并到新数组中，而是要求合并到nums1中，题目中已经将空间开好

思路2：采用三指针，i1和i2从后往前进行比较，例如开始时：

i1指向nums1中的3，i2指向nums2末尾的6，j指向nums1末尾的0；

3<6,将i2指向的值给了j，然后i2–，j–；

i1暂时不需要向前偏移，将继续和i2指向的下一个位置进行比较

如上图，我们采取，指针从后逐渐向前偏移的方式，使得nums2从后往前放到nums1后面，但是通过画图，我们发现会出现两种情况：

1.当i2先走完，这时nums1中的元素就是合并后的结果。

2.当i1先走完，这时，需要将nums2中剩余的值放到nums1中，此时的nums1才是最后的结果。

最终代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int i1 = m-1,i2 = n-1;
    int j = m+n-1;
    while(i1 >= 0 && i2 >=0)//不满足一个条件就结束
    {
        if(nums1[i1] > nums2[i2])
        {
            nums1[j--] = nums1[i1--];
            //相当于
            //nums1[j] = nums1[i1];
            //j--;
            //i1--;
        } 
        else
        {
            nums1[j--] = nums2[i2--];
        }
    }
    while(i2 >=0)//当i1走完，i2未走完
    {
        nums1[j--] = nums2[i2--];
    }
}