【剑指offer|图解|双指针】移除元素 + 合并两个有序数组

🌈个人主页：聆风吟
🔥系列专栏：数据结构、算法模板、汇编语言
🔖少年有梦不应止于心动，更要付诸行动。

---

📋前言

    💬 hello! 小伙伴们大家好哇，上期我们通过图文已经对顺序表进行了详细解析，相信小伙伴们已经对顺序表有的初步了解，今天我们在结合两道道面试题对顺序表进一步巩固，如果有需要复习的小伙伴可以点击此处链接《图解顺序表》跳转过去对顺序表进行回顾。
    📚 系列专栏：本期文章收录在《剑指offer每日一练》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

---

一. ⛳️移除元素

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

• 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
• 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

输入： nums = [ 3, 2, 2, 3 ], val = 3
输出： 2, nums = [ 2, 2 ]
说明： 函数应该返回新的长度 2 , 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

限制：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

解题思路：
双指针解法
定义双指针 pre 和 cur 分别位于数组的起始端，使用指针cur遍历数组nums：

1. 如果nums[cur] == val，则执行cur自增加1；
2. 如果nums[cur] ！= val，则执行nums[pre++] = nums[cur]，并执行cur自增加1。
3. 当cur指向数组的末尾时，终止循环，返回pre即可;

c++代码：

int removeElement(int* nums, int numsSize, int val){
    //初始化两个指针，分别指向数组初始位置
    int pre = 0;
    int cur = 0;

    //循环
    for(cur = 0; cur < numsSize; cur++)
    {
        if(nums[cur] != val) nums[pre++] = nums[cur];
    }

    //返回结果
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

二. ⛳️合并两个有序数组

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

题目：
给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数 m 和 n ，分别表示nums1和nums2中的元素数目。请你合并nums2 到nums1中，使合并后的数组同样按非递减顺序排列。

注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例：

输入： nums1 = [ 1, 2, 3, 0, 0, 0 ], m = 3, nums2 = [ 2, 5, 6 ], n = 3
输出： [ 1, 2, 2, 3, 5, 6 ]

限制：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

解题思路：
双指针

1.初始化： 定义三个指针end1，end，end2分别指向数组num1的有效元素的位置、以及num1和num2的最后位置。

2.循环：

• 如果nums1[end1] > nums2[end2]，执行nums1[end--] = nums2[end2--]；
• 如果nums1[end1] <= nums2[end2]，执行nums1[end--] = nums1[end1--]；
• 如果end1 或 end2 其中一个小于0，循环终止。

3.判断end2是否小于零：

• 如果为小于零，不进行任何操作；
• 如果大于等于零，将nums2中的剩余的元素压入nums1中。

c++代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    //初始化
    int end = m + n -1;
    int end1 = m -1;
    int end2 = n - 1;

    //循环
    while(end1 >= 0 && end2 >= 0)
    {
        if(nums1[end1] > nums2[end2])
        {
            nums1[end--] = nums1[end1--];
        }
        else
        {
            nums1[end--] = nums2[end2--];
        }
    }

    //判断end2的值
    while(end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}
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

---

📝全文总结

本文主要讲解：
    本文结合两道题目对顺表的考察方向有的初步了解，主要也是结合其他算法对数组进行相关操作。觉得不过瘾的小伙伴可以去牛客或者leetcode多找写相关题目进行练习，多做多练总会有好处的。

     今天的内容就到这里了，你对今天的内容是否有所掌握？如果还有疑问的话请在评论区里多多提问，大家可以一起帮你解决，让我们共同进步。创作不易，如果对你有用的的话点个赞支持下作者，你们的支持是作者创作最大的动力。关注我不迷路，让我们下期再见✋✋。