初刷leetcode题目(5)——数据结构与算法

😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️
💥个人主页：🔥🔥🔥大魔王🔥🔥🔥
💥所属专栏：🔥魔王的修炼之路–数据结构🔥
如果你觉得这篇文章对你有帮助，请在文章结尾处留下你的点赞👍和关注💖，支持一下博主。同时记得收藏✨这篇文章，方便以后重新阅读。

五、88. 合并两个有序数组

88. 合并两个有序数组

思路

非递减顺序：意思就是递增，只不过可能会出现重复项，所以不是完全意义的递增，所以说是非递减顺序。
题目分析：题目要求仍然要按顺序进行两个数组的合并排列，并且合并后是储存在第一个数组中的，第一个数组的大小是第一个数组元素的个数的字节数加第二个数组元素的个数的字节数，也就是如果数组1的元素个数为m，数组2的元素个数为n，那么数组1能存放的元素的个数就是m+n。
提供两种解法：
第一种：
开辟一个新数组空间，大小为数组1的大小，因为数组1的大小是两个数组元素的和，然后用双（三）指针（为什么是三：因为新数组的操纵也要用到一个指针）（和前面的那两题不同，前面那两题是双指针指向同一个数组，这里是分别指向一个数组），都从第一个元素开始，相比较，小的赋给第三个数组，然后第三个数组的指针和指向数小的那个指针都指向下一个元素，然后继续判断，直到有一个结束，那么剩下的操作就是把没有结束的那个数组剩下的元素赋给第三个数组，然后把第三个数组拷贝到第一个数组。
第二种：
因为数组1直接就是1、2数组元素个数整体的大小，那么我们不妨从后面（让两个数组都从最后开始比较大小，然后赋值也是从数组1的最后边开始）开始操纵，从大到小排序，让大的放到数组1的最后面，然后一直进行这样的操作（不会出现还没有判断大小就被覆盖的情况），直到把指针指向的第一个元素判断完，然后把剩下没判断完的那个数组中没判断的元素依次赋过去。当然，如果是数组2判断完了，数组1没判断完，那么就不用执行这一步骤了，因为数组1本来就是递增排序的，再怎么排序也还是这个顺序，但是如果数组2没判断完，数组1提前结束了，那就需要把数组2的覆盖到数组1前面的位置。

代码

第一种

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* nums3 = malloc(sizeof(int)*(m+n));
    int n1 = 0;
    int n2 = 0;
    int n3 = 0;
    while(n1 < m && n2 < n)
    {
        if(nums1[n1]<nums2[n2])
        {
            nums3[n3] = nums1[n1];
            n1++;
            n3++;
        }
        else
        {
            nums3[n3] = nums2[n2];
            n2++;
            n3++;
        }
    }
    if(n1==m)
    {
        while(n2<n){
        nums3[n3] = nums2[n2];
        n2++;
        n3++;
        }
    }
    else
    {
        while(n1<m)
        {
            nums3[n3] = nums1[n1];
            n1++;
            n3++;
        }
    }
    memcpy(nums1,nums3,sizeof(int)*(m+n));
}
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
37
38
39

第二种

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int dst = m + n - 1;
    int src1 = m - 1;
    int src2 = n - 1;
    while (src1 >= 0 && src2 >= 0)
    {
        if (nums1[src1] > nums2[src2])
        {
            nums1[dst] = nums1[src1];
            src1--;
            dst--;
        }
        else
        {
            nums1[dst] = nums2[src2];
            src2--;
            dst--;
        }
    }
    if (src1 == -1)
    {
        while (src2 >= 0)
        {
            nums1[dst--] = nums2[src2--];
        }
    }
}
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

• 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。

🌈专栏推荐
😈魔王的修炼之路–C语言
😈魔王的修炼之路–数据结构初阶
😈魔王的修炼之路–C++
😈魔王的修炼之路–Linux
更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。