双指针原地修改数组（力扣原题分析）

题1：Leetcode27——移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用** O(1) **额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

链接：Leetcode27

示例

示例 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]，也会被视作正确答案。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3]
解释：
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示

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

核心代码模式

int removeElement(int* nums, int numsSize, int val)
{

}

思路分析与代码实现（C语言）

1.双指针原地修改法

定义两个下标src和dst，欸你这也不是指针啊，是不是骗人？非也，用数组下标在逻辑思路上和使用指针没什么区别。src遍历数组，dst用来“封口”，也就是用src检测元素是不是val，不是的话就不用移除，那就把它放在dst管理的子数组中，然后dst自增1，看起来是不是就像src在装载货物到袋子中？dst就是袋口，装到最后没东西装了就装完了，dst就用来“封口”了。
相当于用dst创了一个数组中的子数组来存储不被删除的元素，最后只需打印这个子数组即可。
这是在原数组上进行的操作，没有额外开辟其他数组，空间复杂度为O(1)，也就是原地修改数组内容。

代码实现

int removeElement(int* nums, int numsSize, int val)
{
    int src = 0;
    int dst = 0;

    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            nums[dst] = nums[src];
            ++dst;
        }

        ++src;
    }

    return dst;
}

2.（本题不适用）辅助数组双指针法

创建两个等大数组，一个用来存储输入的原序列，另一个用来存储删除了指定数字的序列。这种思路不用考虑序列顺序，直接遍历原序列数组，一个一个同要删除的数字进行比对，如果是目标数字就继续循环，不是目标数字的话就将其按下标顺序放入新序列数组，最后输出新序列数组。这样做不需要特地查找目标数字，一个循环遍历就可以完成数组移植，要删除的数字不会放入新数组，简单清晰地完成要求。
额外开辟一个和原数组等大的辅助数组，定义下标src对应原数组，dst对应辅助数组，只要src没“走”到原数组末尾就一直循环，每轮循环的最后src自增1向后移动，在循环中，若src遇到的元素和val不同，就把元素放入辅助数组，dst再自增1向后移动，若src遇到的元素与val相同，则什么也不干，src找下一个元素。如此一来，不用移除的元素全部按原来的顺序放入了辅助数组中，要移除的元素则没有放入。最后再把辅助数组的元素拷贝到原数组去。

代码实现

int removeElement(int* nums, int numsSize, int val)
{
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    int src = 0;
    int dst = 0;

    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            tmp[dst] = nums[src];
            ++dst;
        }
        ++src;
    }

    for(int i = 0; i < dst; i++)
        nums[i] = tmp[i];
    return dst;
}

## 题2：Leetcode26——移除有序数组中的重复项 ### 题目描述给你一个升序排列的数组 nums ，请你 **原地**删除重复出现的元素，使每个元素**只出现一次** ，返回删除后数组的新长度。元素的**相对顺序应该保持一致**。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 **原地** 修改输入数组，并在使用 **O(1)** 额外空间的条件下完成。

链接：Leetcode26

示例

示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2]
解释：
函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4]
解释：
函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示

1 <= nums.length <= 3 * 104
-104<= nums[i] <= 104
nums 已按升序排列

核心代码模式

int removeDuplicates(int* nums, int numsSize)
{

}

思路分析与代码实现（C语言）

双指针原地修改法

实际上和上一道题思路十分的类似，还是定义两个下标，src对应原数组，dst对应子数组，还是遍历一遍数组，不过这一题的判断条件要改改——判断src遇到的元素是否和dst对应的元素相同，相同的不要，直接跳过，遇到不同的才放入dst管理的子数组，直到src把原数组访问完毕。不过要注意的是，src遇到不同的元素时，要先让dst自增1再把nums[src]赋值给nums[dst]，dst直接指向的是子数组的最后一个元素（这和上一题不一样），所以最后返回值时要让dst加个1。

代码实现

int removeDuplicates(int* nums, int numsSize)
{
    int src = 0;
    int dst = 0;
    
    while(src < numsSize)
    {
        if(nums[src] != nums[dst])
        {
            ++dst;//
            nums[dst] = nums[src]; 
        }

        ++src;
    }

    return dst + 1;
}

题3：Leetcode88——合并两个有序数组

题目描述

给你两个按 **非递减顺序 **排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

链接：Leetcode88

示例

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6]
解释：
需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：
输入：nums1 = [1], m = 1, nums2 = [ ], n = 0 输出：[1]
解释：
需要合并 [1] 和 [ ] 。合并结果是 [1] 。

示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1]
解释：
需要合并的数组是 [ ] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示

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

进阶
你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

核心代码模式

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{

}

思路分析与代码实现（C语言）

多指针原地修改法

欸，不是双指针的吗，怎么变成了多指针呢？这道题有点特殊，如果还是只用两个指针，可能会比较麻烦，我们设计多一个辅助指针，用逆向的思维来高效解决这道题。
实际上这道题有一个用空间换时间的思路，可以开辟一个辅助数组，然后用两个下标分别指向两个数组nums1和nums2，按照从前往后的顺序比较两个数组的的元素的大小，小的先放入辅助数组中，大的继续和后面的元素比较，当全部元素移动完以后，再把辅助数组元素拷贝给nums1数组，这样一来空间复杂度就为O(m+n)，那有没有更省空间的办法，就是说能不能原地修改呢？
如果说，我们参考上面那个空间换时间的的思路来原地修改，从前往后比较两个数组的元素大小，就有可能造成元素覆盖丢失元素，就比如说nums1为1, 2, 5而nums2为3, 3, 4，就会让nums2中的第一个3把nums1中的5给覆盖掉。所以说，我们得另寻他法。
那我们不妨逆向思维一波，既然从前往后会覆盖，那么从后往前呢？
定义两个下标p1和p2，分别对应数组nums1和nums2，再定义一个下标cur从nums1的末尾开始，每放入一个元素就向前移动一位，而p1和p2从两个数组最后面的有效元素开始，向前移动，比较两个数组的元素的大小，注意啦，这里是要把大的那个拿出来放到cur指向的位置。
不过，移到后面会发现有两种情况：
情况1是数组nums2的元素先移动完，这时候整个过程就可以结束了，如图：

情况2是数组nums1的元素先移动完，此时nums2数组还有元素没有移动，所以还需要附加上一个把nums2剩余元素移动到nums1中的过程，如图：

代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int p1 = m - 1;
    int p2 = n - 1;
    int cur = m + n - 1;

    while(p1 >= 0 && p2 >= 0)
    {
        if(nums1[p1] > nums2[p2])
            nums1[cur--] = nums1[p1--];
        else
            nums1[cur--] = nums2[p2--];
    }

    while(p2 >= 0)
        nums1[cur--] = nums2[p2--];

}