问题描述
原题链接：https://leetcode.cn/problems/remove-element/
解题方案
思路一
思路一：
首先通过简单分析，很明显这是一道顺序表相关问题。首先能够想到的是暴力求解，即思路一：找到所有的val，每次挪动val后的数据覆盖删除val。
📝代码展示：
int find(int*nums,int numsSize,int val) { int i=0; for(i=0;i<numsSize;i++) { if(nums[i]==val) return i; } return -1; } int removeElement(int* nums, int numsSize, int val) { int ret; while((ret=find(nums,numsSize,val))!=-1) { for(int i=ret;i<numsSize-1;i++) { nums[i]=nums[i+1]; } numsSize--; } return numsSize; }
但是对于思路一，空间复杂度显然是O(1)，当我们计算时间复杂度的时候，最坏的情况是数组中大部分值都为val，这时时间复杂度近似为O(1+2+……+n-1)即O(n^2)，显然O(n^2)的时间复杂度还是不尽人意，本着降低时间复杂度，我们可以怎样优化呢？
思路二
思路二：
在创建一个临时数组tmp，遍历nums数组，把不是val的数值放到tmp数组，最后把tmp数组的内容依次拷贝到nums数组，返回tmp数组长度。
📝代码展示：
int removeElement(int* nums, int numsSize, int val) { if(numsSize==0)//特殊处理 return 0; int i=0; int tmp[numsSize]; int count=0; for(i=0;i<numsSize;i++) { if(nums[i]!=val) { tmp[count]=nums[i]; count++; } } for(i=0;i<numsSize;i++) { nums[i]=tmp[i]; } return count; }
注释：这里的特殊处理是因为在函数中使用了变长数组 int tmp[numsSize];而变长数组的大小不能为0，这是使用特殊处理，是因为力扣的测试用例中含有[] 0。
对于思路二，最坏的情况我们只遍历了1遍数组，即时间复杂度为O(n)，但是这明显是一种用空间换区时间的方法，在此过程我们创建了numsSize个变量，即空间复杂度为O(n)。所以我们能不能通过再降低空间复杂度，进一步优化呢？
思路三(最优解)
思路三：
创建两个变量src、dest，初始时指向首部，判断nums[src]是否等于val，如果等于val则dest指向不动，src向后偏移，直到nums[src]!=val，令nums[dest]=nums[src]，然后src、dest都向后偏移，直到src遍历完数组，程序结束。
📝代码展示：
int removeElement(int* nums, int numsSize, int val) { int src=0; int dest=0; while(src<numsSize) { if(nums[src]!=val) { nums[dest]=nums[src]; src++; dest++; } else src++; } return dest; }
这种思路下时间复杂度为遍历整个数组O(n)，创建的变量为有限个，所以空间复杂度为O(1)。相比之下为最优解。
总结：
总的来说这并不是一道难题，那为什么要拿出这道题介绍？拿出这道题真正想要传达的是解题的思路，以及不断优化探寻最优解的过程。希望通过这道题能给你带来一种解题优化的思路。感谢阅读！
