一、题目
1、原题链接
27. 移除元素
2、题目描述
二、解题报告
1、思路分析
暴力解法
利用两层循环，第一层循环找到值等于val的元素，第二层循环“移除元素”。（数组移除元素就是将该位置后面的元素依次向前移动一个位置，从而达到“移除”的效果，注意移动的顺序：应该从待移动序列前往后依次向前移动，否则会造成数组元素值“丢失”）
双指针法
设置两个指针，快指针用来遍历数组，慢指针用来找到值为val的元素。具体流程：快指针和慢指针初始指向数组中第一个元素，然后快指针向后遍历数组，当数组元素的值不等于val时，慢指针也向后移动，同时记录该元素在数组中；如果数组元素的值等于val时，慢指针不动，快指针继续向后遍历，直到数组元素的值不等于val时，执行前述操作。直至快指针遍历完整个数组。算法结束，此时慢指针正好记录了移除重复元素后的数组长度。
2、时间复杂度
暴力解法时间复杂度O(n^2)
双指针法时间复杂度O(n)
3、代码详解
暴力解法代码
class Solution { public: int removeElement(vector<int>& nums, int val) { int cnt = nums.size(); //注意循环条件i<cnt，不要写成i<nums.size()造成错误 for (int i = 0; i < cnt; i++) { if (nums[i] == val) { //“移除”过程：i位置后的所有元素向前移动一个位置 for (int j = i + 1; j < cnt; j++) { nums[j-1] = nums[j]; } cnt--; //i后面元素都向前移动了一个位置，i也向前移动一个位置 //下一次循环时相当于i没有动，而元素向前移动了一个位置 //i也就指向了下一个需要遍历的数组元素 i--; } } return cnt; } };
双指针法代码
class Solution { public: int removeElement(vector<int>& nums, int val) { int slowPoint=0; //快指针遍历数组 for (int fastPoint = 0; fastPoint < nums.size(); fastPoint++) { //慢指针记录结果：只记录值不为val的所有元素 if (nums[fastPoint] != val) { nums[slowPoint++]=nums[fastPoint]; } } //此时slowPoint正好记录了移除重复元素后的数组元素个数 return slowPoint; } };
三、知识风暴
双指针法
