【C/C++练习】经典的快慢指针问题—移除元素

题目描述

题目出处：移除元素

示例

题解

 对于本题我将按照由易到难的顺序为大家分享三种解题思路，并逐一分析它们的优劣，以及注意事项。

思路一：暴力求解

 我想暴力求解应该是第一次接触到此题的小伙伴们最先想出来的办法吧。这道题目暴力求解就是去遍历数组，当遇到数组元素等于val的时候，将后面的所有元素往前挪动一位，把val覆盖掉以实现移除的效果。具体过程如下动图所演示：

代码实现：

int removeElement(int* nums, int numsSize, int val){int i = 0;int len = numsSize;while(i < len)//循环控制变量用len，因为如果有重复，就会往前覆盖{if (nums[i] == val){int j = 0;for (j = i; j < len; j++)//把后面的往前覆盖{if (j != numsSize - 1){nums[j] = nums[j + 1];}}len--;//找到一个之后跳出循环，继续从下标为0的数字开始检查}else{i++;}}return len;}

 需要注意：i是用来遍历整个数组的，当nums[i] == val的时候停下来，把i后面的所有数据往前挪动一位，且数组的有效长度len减一。挪动完后i的值不变，因为此时i位置上的元素是它后一位经过挪动覆盖过来的，我们并不知道他是否等于val，因此需要继续判断num[i]是否等于val，如果不等于再让i++继续去遍历后面的元素，直到i等于数组的有效长度，此时说明已经遍历结束。

复杂度分析：
时间复杂度要讨论最坏的情况，对于本题最坏情况就是数组中所有的元素都等于val，假设数组一共有$N$个元素，那么将第一个元素移除需要把后面的$N-1$个元素全部往前挪动一位，也就是挪动$N-1$次，由于数组元素全是val所以经过挪动后第一个元素任然是val，但此时数组的有效元素个数已经变成了$N-1$，所以此时需要挪动$N-2$…以此类推总的挪动次数就是一个等差数列求和，因此时间复杂度就是 O ( N2)O(N^2)O(N2)

思路二：空间换时间

 如果对空间复杂度没有要求的情况下，我们可以创建一个新数组，然后去遍历原数组，如果num[i]不等于val就把他拷贝到新数组，如果等于那就跳过并且有效数据个数减一，直到遍历结束，然后把新开数组的内容拷贝回原数组。具体过程如下动图所示：

代码实现：

int removeElement(int* nums, int numsSize, int val){int len = 0;int* tmp = (int*)malloc(sizeof(int)*numsSize);for(int i = 0; i < numsSize; i++){if(nums[i] != val){tmp[len++] = nums[i]; }}memcpy(nums, tmp, sizeof(int)*len);return len;}

复杂度分析：
时间复杂度方面，这种方案只遍历了一遍数组，因此它的时间复杂度是$O(N)$，在空间复杂度方面，由于开辟了一个新数组，所以空间复杂度是$O(N)$。

思路三：双指针

 这种思路的具体过程是：同时维护两个指针，分别记作pri和pos，让他俩从第一个元素开始同时往后走，当pos指向的元素不等于val的时候，把其赋值给pri所指向的位置，然后两个指针继续往后走，如果pos指向的元素等于val，那么pri停下来，pos跳过这个元素继续往后走，直到pos指向的元素不等于val，把它赋值给pri指向的位置，然后两个指针继续同时往后走，直到pos指针来到数组的结尾。具体过程如下动图所示：

代码实现：

int removeElement(int* nums, int numsSize, int val){int pri = 0, pos = 0;while(pos < numsSize){if(nums[pos] != val){nums[pri] = nums[pos];pri++;}pos++;}return pri;}

复杂度分析：
在时间复杂度方面，这种方法只遍历了一遍数组，所以时间复杂度是$O(N)$，在空间复杂度方面，由于没有额外申请空间所以空间复杂度是$O(1)$。对于这道题思路三无疑是最好的方法，这种快慢指针的思想大家要多多去体会。

题目描述

题目出处：删除有序数组中的重复项

题解

 有了上面的分析基础，我们应该很容易猜到这道题也可以使用双指针的方法来做，但是这个题的双指针与上面的又有所不同。这道题要让pri指针从第一个元素开始，pos指针从第二个元素开始，因为相同的元素只需要保存一个，如果pos指向的元素与pri指向的元素相等就让pos往后走而pri不动，直到pos指向的元素不等于pri指向的元素，此时先让pri往后走一步，然后把pos指向的元素赋值给pri指向的元素，具体过程如下动图所示：

代码实现：

int removeDuplicates(int* nums, int numsSize){int pri = 0;int pos = pri + 1;while(pos < numsSize){if(nums[pos] != nums[pri]){pri++;nums[pri] = nums[pos];}pos++;}return ++pri;}

 今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是春人前进的动力！