leetCode 27. Remove Element

[27. Remove Element]

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

思路

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

暴力解法

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

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

  空间复杂度：O(1)

双指针法

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

class Solution {public:    int removeElement(vector& 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)