[27. Remove Element]

[(https://leetcode.cn/problems/remove-element/)

思路

• 数组在内存中是连续的，根据此题要求不能删除，而是覆盖

暴力解法

• 此题暴力解法是两层for循环，一个循环遍历数组元素 ，第二个循环更新数组

• 时间复杂度：O(n^2)

  空间复杂度：O(1)

双指针法

• 双指针法：又叫快慢指针法， 一个快指针和慢指针在一个for循环下完成两个for循环的工作
• 首先，我们需要定义双指针的含义：
  • 快指针：寻找新数组（不含有val）的元素
  • 慢指针：指向新数组的下标

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size() == 0) return 0;
        int slowindex = 0, fastindex = 0;	//定义快慢指针
        for(; fastindex < nums.size(); ++fastindex)		//因为快指针是寻找新元素，因此需限定快指针范围
        {
            //若寻找的此新元素等于val，则跳过
            if(nums[fastindex] != val)
            {
                nums[slowindex++] = nums[fastindex];
            }
        }
        return slowindex;	//因为慢指针是指向新数组的下标，因此只需返回慢指针索引值
    }
};

• 时间复杂度：O(n)

  空间复杂度：O(1)