LeetCode 顺序表练习：移除元素、删除重复项与合并有序数组

可以看到最后通过了，我们来分析一下代码的时间复杂度和空间复杂度。第一个和第二个 for 循环都是 O(N)，关键在于第二个 while 循环的时间复杂度。

由于我们的查找方法和删除方法时间复杂度都是 O(N)，外层有一个 while 循环，所以时间复杂度就是 O(N^2)。

接着来看空间复杂度，我们为了在顺序表中操作数组的数据，所以把数组中的数组全部放入了顺序表，所以顺序表会额外开辟数组元素大小的空间，空间复杂度为 O(N)。

我们知道这个时间复杂度和空间复杂度都不是很好，所以我们还有另外一种优化的方法。

方法 2（双指针）

这里的双指针并不是创建两个指针变量，而是数组中的下标，因为数组中我们能够通过下标来访问元素，与指针相似，所以叫做双指针。

具体方法就是创建两个整型变量 src 和 dest，src 代表源，dest 代表目的地。

在双指针算法中，我们的思路很简单，就是首先让 src 和 dest 都指向数组的第一个元素，随后我们就看 src 位置上的值是否是题目给出的 val，如果是我们就直接让 src 往后走一步。

如果不是，我们就把 src 位置上的值赋给 dest，随后让 dest 和 src 都往后走一步。

有了上面的分析，我们就可以有一些思路了，首先创建两个整型变量 src 和 dest 作为我们的双指针，初始情况下让它们都为 0。

随后创建一个循环，循环条件就是 src < numsSize，因为 src 是数组中的下标，要保证它不能越界，接着我们就进行判断，如果 src 位置的值等于 dest 位置的值，那么直接让 src++。

否则的话就是不等于，那么把 src 位置的值赋值到 dest 位置，随后让它们都 ++，如下：

int removeElement(int* nums, int numsSize, int val) {
    // 循环条件 src < numsSize
    int src = 0, dest = 0;
    while (src < numsSize) {
        if (nums[src] == val) {
            src++;
        } else {
            nums[dest++] = nums[src++];
        }
    }
    // 循环结束，dest 就是指向最后一个元素的后一个，就是元素个数
    return dest;
}

最后我们提交一下就通过了，在双指针方法中，我们只有一个循环，时间复杂度为 O(N)，申请的空间也是常数个，所以空间复杂度为 O(1)，可以看到比使用顺序表的方法简便多了，时间复杂度和空间复杂度都优化了一个档次。

这道题的双指针法的本质就是探路法，碰到了指定的元素就不管，直接跳过，然后把不是指定的元素放在前面，简单地说就是一个在前面探路，一个在后面接收。

2. 删除有序数组中的重复项

题目链接：删除有序数组的重复项

方法 1（顺序表）

既然我们的标题是顺序表练习，那我们第一种方法还是用顺序表来做。

根据上面图片的解释，我们大致明白了题目的要求，就是数组是相对有序的，然后我们要删除那些重复项，让数组里面的元素变得唯一且有序，最后返回唯一的元素个数，至于其它位置的元素就不管了。

首先还是把顺序表拷贝过来，以及初始化，销毁，这些都不要忘记，然后把数组数据尾插到顺序表中上面讲过了，接着我们就来讲这道题不同的地方。

由于数组是相对有序的，所以相同的元素肯定是放在一起的，所以我们就可以写一个循环来判断前后两个元素是否相等，如果相等我们就删除当前的元素，每删除一个元素 numsSize 就减 1，要特别注意的一个点是要保证下标的有效性，如下：

for (i = 0; i < numsSize; i++) {
    if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]) {
        SLErase(&sl, i);
        numsSize--;
    }
}

但是我们的代码通过不了这个测试用例。

来调试一下看看问题出在哪里。

这个时候我们发现了问题，当 i = 1 时，将下标为 1 的元素删除了，所有后面的其它元素都往前挪动了一步，导致现在下标为 1 和 2 的元素又相等了。

但是本次循环结束了，下一次在循环中 i 要++变成了 2，i+1 变成了 3，比较不了下标为 1 和 2 的元素了，也就导致了下标为 1 和 2 的元素相等没有处理。

那么怎么解决呢？其实也很简单，问题就出在删除一个相同元素后，其余元素都往前挪动了，但是循环结束了，i 要++，就不会再比较移动后的 i 下标位置的元素和 i+1 下标的元素了。

所以我们为了能够让它删除元素后，多比较一次原本移动后的 i 下标位置的元素和 i+1 下标的元素，我们可以在删除一个元素后让 i--，这样处理后下次进入循环 i 的值就不会变化，代码如下：

for (i = 0; i < numsSize; i++) {
    if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]) {
        SLErase(&sl, i);
        numsSize--;
        i--;
    }
}

当完成上面的步骤之后我们再把顺序表中的数据拷贝回原数组中，此时的 numsSize 就是有效的元素个数。

int removeDuplicates(int* nums, int numsSize) {
    SL sl;
    int i = 0;
    SLInit(&sl);
    for (i = 0; i < numsSize; i++) {
        SLPushBack(&sl, nums[i]);
    }
    for (i = 0; i < numsSize; i++) {
        if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1]) {
            SLErase(&sl, i);
            numsSize--;
            i--;
        }
    }
    for (i = 0; i < numsSize; i++) {
        nums[i] = sl.arr[i];
    }
    SLDestroy(&sl);
    return numsSize;
}

最后我们提交一下就可以通过了，在这个方法中，我们的时间复杂度也是很高的，达到了 O(N^2)，并且由于使用顺序表拷贝了原数组中的内容，空间复杂度也不低，达到了 O(N)，所以我们接下来介绍一个更好的方法。

方法 2（双指针）

这道题还是可以使用我们的双指针法来做，上一题的本质就是探路法。

这道题也可以借鉴这样的思想，我们题目要求去掉相对有序的数组中的元素，说明相等的元素都是挨在一起的，我们还是可以定义两个变量 src 和 dest，src 在前面探路，dest 在后面接收。

具体思路就是：初始情况下让 dest 指向第一个元素，而 src 指向第二个元素，因为如果它们都指向第一个元素，那么它们肯定就相等了，没有比较的必要，所以让 src 走到第二个元素的位置上。

然后我们就比较 src 和 dest 位置上的元素是否相等，如果相等我们就让 src++，其它什么都不做，如果不相等就让 dest++，然后把 src 位置的值赋值到 dest 位置上，然后再让 src++。

具体的例子我们就参考题目给出的第一个示例。

有了上图的解析，我们现在就可以直接来写代码了，首先创建一个 while 循环，循环条件就是 src < numsSize。

然后如果 src 指向的元素等于 dest 指向的元素，就让 src++，其它什么都不做，如果不相等，就让 dest 先++，再把 src 位置的元素赋值给 dest 位置的元素，最后让 src++，如下：

while (src < numsSize) {
    if (nums[src] == nums[dest]) {
        src++;
    } else {
        dest++;
        nums[dest] = nums[src];
        src++;
    }
}

最后循环结束返回 dest + 1。

int removeDuplicates(int* nums, int numsSize) {
    int src = 0, dest = 0;
    while (src < numsSize) {
        if (nums[src] == nums[dest]) src++;
        else nums[++dest] = nums[src++];
    }
    return dest + 1;
}

最后也是成功提交了代码，我们来分析一下双指针法的时间复杂度和空间复杂度，我们只用了一个循环，时间复杂度为 O(N)，也没有额外申请空间，所以空间复杂度为 O(1)。

3. 双指针练习之合并两个有序数组

题目链接：合并两个有序数组

方法 1（直接排序）

先来解读一下题目，题目给了我们两个数组，其中第一个 nums1 的大小是两个数组的和（m+n），因为我们要将 nums2 合并到 nums1 中去，要保证空间足够，所以题目才给出这样的条件。

首先题目告诉我们两个数组都是非递减的数组，所以有两种可能，一是递增，二就是可能是重复数据，现在题目要求我们将他俩合并成有序数组返回。

第一个和方法就是，直接将 nums2 拷贝到 nums1 中，再对 nums1 进行排序，我们可以使用 qsort 函数实现排序。

代码的实现过程就不再多讲了，思路很简单，这里我们直接给出完整代码：

#include <stdlib.h>

// 这个函数的意思就是比较数组中的元素大小
int int_compare(const void* e1, const void* e2) {
    return *(int*)e1 - *(int*)e2; // 前 - 后<0 就是升序
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 将 nums2 放进 nums1，所以循环条件应该小于 n
    for (int i = 0; i < n; i++) {
        nums1[i + m] = nums2[i]; // 这里是将 nums2 放在 nums1 的 m 位置之后
    }
    qsort(nums1, m + n, sizeof(int), int_compare);
}

可以看到代码逻辑还是相对简单的，并且效率也很高，因为这里的 qsort 使用的是快排，时间复杂度仅仅是 O(N*logN)，空间复杂度是 O(1)，但是我们下面还有一个办法使它更快一点，那就还是我们的双指针法。

方法 2（双指针）

其实我们这三道题都很类似，所以双指针很吃香，只不过在这道题中，我们有两个数组需要合并，我们还是可以试着用之前的思路来思考一下这个题，上面的题是一个数组，而这一道题是两个数组，那我就可以定义两个指针 src1 和 src2。

之前的思路就是，如果碰到相同的元素，或者题目给出的元素，我们就把他给跳过，使用后面的元素把它覆盖，那这道题就有一些不一样的地方。

首先第一个思路就是 src1 指向 nums1 的第一个元素，src2 指向 nums2 的第一个元素，由于最后的结果要保存在 nums1 中，所以我们把 dest 定义在 nums1 中，指向 nums1 的第一个位置。

随后我们比较 src1 指向的元素和 src2 指向的元素哪个小，哪个小就把它放到 dest 的位置上，然后让 dest++，然后 src1++或者 src2++，最后循环这个步骤。

但是我们最后发现这个思路有点问题，问题出在 nums1 数组中，因为如果我们直接把数据放在 dest，也就是从 nums1 数组的开头开始存放数据，会导致原本的 nums1 数组的数据被覆盖，我们举个例子。

这个时候我们发现问题了，nums1 中的数据会被覆盖，所以第一种思路并不可行，那么应该怎样改进，避免数据被覆盖呢？这个时候我们不放换一个思路，倒过来想，既然放小的不行，那咱们就放大的，也就是从 nums1 的最后开始放数据，也就是让我们的 dest 指向 nums1 的最后一个位置。

因为我们要保证 nums1 最后排序成相对递增，最后一个位置就要放最大值，我们可以让 src1 和 src2 分别指向 nums1 和 nums2 的最后一个元素，然后比较谁大谁就放在 dest 的位置。

然后让 dest–，以及 src1- -或者 src2- -，就这样一直找大放在 dest 的位置，循环条件就是要让 src1 和 src2 都大于 0，因为都是数组下标，都不能越界。

可以看到我们这里将两个数组合并到了 nums1 中，让数组 nums1 有序了，但是其实有一个问题，如果我们最后是 src2 先越界，那么说明 nums2 数组中的数据已经全部放入 nums1 了，循环结束了，剩下的 nums1 的数据也已经保持了有序，所以 src2 首先越界代码没有问题。

但是有可能下一次 src1 首先越界，说明 nums1 中原本的有效的元素已经放在 nums1 数组后面了，循环结束了，但是 nums2 数组还没有放完呀，这个时候就会出错，所以我们还需要在这个循环结束后用一个新的循环判断一下。

如果 src2 还大于等于 0，说明 nums2 数组中的内容还没有全部移动到 nums1 中，此时我们只需要循环地让数组 nums2 中的元素移动到 nums1 的 dest 位置，接下来我们的代码才能完全没问题，如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int src1 = m - 1;
    int src2 = n - 1;
    int dest = m + n - 1; // nums1 的最后一个位置
    
    while (src1 >= 0 && src2 >= 0) {
        // 单纯的比大小，谁大就放谁
        if (nums1[src1] < nums2[src2]) {
            nums1[dest--] = nums2[src2--];
        } else {
            nums1[dest--] = nums1[src1--];
        }
    }
    
    // 如果 nums2 还没有走完
    while (src2 >= 0) {
        // 将 nums2 的元素全部放进 nums1 的 dest 位置
        nums1[dest--] = nums2[src2--];
    }
}

成功拿下，我们再来分析一下这个代码的时间复杂度和空间复杂度，可以发现我们虽然有两个循环，但是实际上深入计算会发现两个循环的次数加起来为 O(N)，所以时间复杂度是标准的 O(N)。

并且由于申请的是有限个空间，所以空间复杂度是 O(1)，我们就可以看出来了，虽然我们的快排很快，时间复杂度仅为 O(N * logN)，但是我们的双指针更快，只有 O(N)。