leetcode移除元素

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

移除元素(原题)

分析

题目要求空间复杂度为O(1),我们先思考用两个数组来进行该过程,再优化空间

• 此处使用big,small为下标,下方数组接收不是目标值的其他元素,big在这里用作遍历的"指针"(非指针),每次都会跳向下一个直到数组结束

• 如果big指向的数组元素不等于目标值,small就要接收并往后移动一格
  

• 下方数组的结果就是我们要得到的结果

• 现在我们要把操作放在同一个数组中进行操作
  

• 始终记得big指针(非指针,只是想说明big指向数组元素形象而已)是用来遍历元素而对数组元素不会改变,small是用来修改数组的,big指针遍历的过程中,big只要指向的不是val元素(看原题),small会覆盖当前值,并向后挪动

题解代码:

c++版本

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int big = 0;
        int small = 0;
        while(big<nums.size())
        {
            if(nums[big] != val)
            nums[small++] = nums[big];
            big++;
        }
        return small;
    }
};

c版本

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