//27.移除数组
//思路1，一个一个判断
#include<assert.h>
void Erase(int* nums, int pos, int len)
{
    //因为题目给的是数组，所以我们要对顺序表的任意删做点改变
    //比如给出第三个参数长度
    assert(len > 0);    //如果长度小于等于0，就报错
    while (pos < len - 1)
    {
        nums[pos] = nums[pos + 1];  //用数组的方式覆盖
        pos++;  //下标++，向后移动
    }
}

int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //nums不能为空指针
    int i = 0;
    int len = numsSize;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] == val)
        {
            Erase(nums, i, numsSize--);
            i--;    //这里要--的原因是防止漏掉val，多判断一次
            len--;  //总长度会-1
        }
    }

    return len; //返回的是删除后的数组长度
}

//27.移除数组
//思路2，以空间换时间
#include<stdlib.h>
#include<assert.h>
int removeElement(int* nums, int numsSize, int val)
{
    int* pa = (int*)malloc(sizeof(int) * numsSize); //动态申请内存
    assert(pa); //预防申请失败的情况
    int i = 0;  //原数组的下标
    int j = 0;  //新数组的下标
    for (i = 0; i < numsSize; i++)
    {
        //如果不是目标值，就将其放入到新数组中
        if (nums[i] != val)
            pa[j++] = nums[i];  //vs中会报一个小警告，原因pa[j]可能会越界，可不管
    }
    //将新数组中的元素注入到原数组中
    for (i = 0; i < j; i++)
        nums[i] = pa[i];

    free(pa);   //释放空间
    pa = NULL;  //指针置空
    return j;   //此时新数组的下标就是有效元素数
}

//27.移除数组
//思路3，双指针覆盖
#include<assert.h>
int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //断言，防止空指针
    int* p1 = nums; 
    int* p2 = nums; //这是两个指针
    //注：直接使用numsSize没事，因为这是局部变量
    while (numsSize--)
    {
        //如果 *p1 != val，就将当前元素向前覆盖
        if (*p1 != val)
            *p2++ = *p1;    //覆盖后，p2要++
        p1++;   //p1需要一直向后移动
    }

    return p2 - nums;   //指针-指针，得到两者间的个数
}

//27.移除数组
//思路4，双指针左右交换版
#include<assert.h>
int removeElement(int* nums, int numsSize, int val)
{
    assert(nums);   //断言，防止空指针
    int* pleft = nums;  //左指针，从数组起始位置开始
    int* pright = nums + numsSize - 1;  //右指针，从数组尾元素位置开始
    while (pleft < pright)
    {
        while (*pleft != val && pleft < pright)
        {
            pleft++;    //左指针向右走
        };
        while (*pright == val && pright > pleft)
        {
            pright--;   //右指针向左走
        };
        if (pleft < pright)
        {
            *pleft ^= *pright;  //因为都是整型元素
            *pright ^= *pleft;  //所以可以用异或交换法
            *pleft++ ^= *pright--;  //其实可以在交换后，让左右指针各走一步
        }
    }
    int len = 0;    //记录返回的长度
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        //如果元素不等于val，长度就可以统计
        if (nums[i] != val)
            len++;
    }
    return len; //返回长度
}