南昌网站建设哪家最好,哪个网站的织梦源码好,WordPress 主页分页,海外网站代理文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、知识风暴 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记#xff0c;如有侵权#xff0c;立即删除。 一、题目
1、原题链接 27. 移除元素 2、题目描述 二、… 文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、知识风暴 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记如有侵权立即删除。 一、题目
1、原题链接 27. 移除元素 2、题目描述 二、解题报告
1、思路分析
暴力解法 利用两层循环第一层循环找到值等于val的元素第二层循环“移除元素”。数组移除元素就是将该位置后面的元素依次向前移动一个位置从而达到“移除”的效果注意移动的顺序应该从待移动序列前往后依次向前移动否则会造成数组元素值“丢失”双指针法 设置两个指针快指针用来遍历数组慢指针用来找到值为val的元素。具体流程快指针和慢指针初始指向数组中第一个元素然后快指针向后遍历数组当数组元素的值不等于val时慢指针也向后移动同时记录该元素在数组中如果数组元素的值等于val时慢指针不动快指针继续向后遍历直到数组元素的值不等于val时执行前述操作。直至快指针遍历完整个数组。算法结束此时慢指针正好记录了移除重复元素后的数组长度。
2、时间复杂度
暴力解法时间复杂度O(n^2) 双指针法时间复杂度O(n)
3、代码详解
暴力解法代码
class Solution {
public:int removeElement(vectorint nums, int val) {int cnt nums.size(); //注意循环条件icnt不要写成inums.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(vectorint nums, int val) {int slowPoint0;//快指针遍历数组for (int fastPoint 0; fastPoint nums.size(); fastPoint) {//慢指针记录结果只记录值不为val的所有元素if (nums[fastPoint] ! val) {nums[slowPoint]nums[fastPoint];}}//此时slowPoint正好记录了移除重复元素后的数组元素个数return slowPoint;}
};三、知识风暴
双指针法
