27.移除元素（LeetCode）

想法一

循环遍历整个数组，碰到数值等于val的元素，后续元素向前挪动一格，将其覆盖

时间复杂度：O(N^2)   空间复杂度：O(1)

想法二

想法一思考起来比较简单，容易想到，但是时间复杂度太高，有没有什么方法可以降低空间复杂度呢？

 以空间换时间：创建一个临时数组，src和dst两个指针。如果src指向的元素不是val，则把src指向的元素拷贝到tmp数组里，src++，dst++；如果是val，则src++,跳过该元素

时间复杂度：O(N)  空间复杂度：O(N)

想法三

想法二的空间复杂度虽然不符合要求，但是给了我们一种新的思路

其实，我们发现不用创建临时数组，直接在原数组进行操作也是可以的 。还是创建src和dst两个指针，当元素为val时，src++，跳过该元素；当src指向的元素不等于val时，将其拷贝到dst指向的空间，src++，dst++，这样就可以覆盖前面为val的元素

对上图分析：0和1都不为val，所以src和dst一起到2，而2为val，则dst留在2，src++，直到3，此时3不为val，则把3拷贝到dst的位置，覆盖之前的2，然后src++，dst++，依此类推

时间复杂度：O(N)   空间复杂度：O(1)

这样，我们就得到了时间与空间共同的较优解

代码如下：

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++];
        }
        else
        {
            src++;
        }
    }
    return dest;
}

这里src和dest是整型变量，代表数组下标，实际上作用也是指针 ，而且返回长度更加方便