cms网站如何修改,公众号里的电影网站怎么做,重庆正云环保建设网站,伊春seo公司一、力扣题目链接
27.移除元素
给你一个数组 nums 和一个值 val#xff0c;你需要 原地 移除所有数值等于 val 的元素#xff0c;并返回移除后数组的新长度。
你不需要考虑数组中超出新长度后面的元素。
二、思路
要知道数组的元素在内存地址中是连续的#xff0c;不…一、力扣题目链接
27.移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
你不需要考虑数组中超出新长度后面的元素。
二、思路
要知道数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖。
2.1暴力解法对于数组是覆盖不是删除
这个题目暴力的解法就是两层for循环一个for循环遍历数组元素 第二个for循环更新数组。
删除过程如下
很明显暴力解法的时间复杂度是O(n^2)这道题目暴力解法在leetcode上是可以过的。
代码如下
// 时间复杂度O(n^2)
// 空间复杂度O(1)
class Solution {
public:int removeElement(vectorint nums, int val) {int size nums.size();for (int i 0; i size; i) {if (nums[i] val) { // 发现需要移除的元素就将数组集体向前移动一位for (int j i 1; j size; j) {nums[j - 1] nums[j];}i--; // 因为下标i以后的数值都向前移动了一位所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};时间复杂度O(n^2)空间复杂度O(1)
2.2双指针法强烈推荐
双指针法快慢指针法 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针侦察兵寻找新数组的元素 新数组就是不含有目标元素的数组慢指针整理员指向更新 新数组下标的位置
很多同学这道题目做的很懵就是不理解 快慢指针究竟都是什么含义所以一定要明确含义后面的思路就更容易理解了。
删除过程如下一个for循环一起走一下不在意谁先走谁后走 双指针法快慢指针法在数组和链表的操作中是非常常见的很多考察数组、链表、字符串等操作的面试题都使用双指针法。
本题代码如下
// 时间复杂度O(n)
// 空间复杂度O(1)
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;for (int fastIndex 0; fastIndex nums.size(); fastIndex) {if (val ! nums[fastIndex]) {nums[slowIndex] nums[fastIndex];// 如果不是要删除的快慢一起走//块赋给慢是因为有时候可能块比慢多走了这个时候俩个指针可以理解为对移除元素视而不见}else{//快指针}}return slowIndex;}
}; 难点正是在于这个if函数而且我们很容易得知快慢指针之间的distance就是val的个数他们做到的其实是对val的一种视而不见遇到val快指针而且慢指针由于只接收快指针的值也视而不见。而且刚开始其实也赋值了只不过自己赋给自己动图没有体现~
注意这个实现方法并没有改变元素的相对位置
时间复杂度O(n)空间复杂度O(1)
2.3容器暴力find大法 class Solution {
public:int removeElement(vectorint nums, int val) {vectorint::iterator itfind(nums.begin(),nums.end(),val);while(it!nums.end()){nums.erase(it);itfind(it,nums.end(),val);//it; 不能这么搞啊 元芳}return nums.size();}
}; 注意val不仅仅只有一个所以得写在while循环里而且find下一次的开始位置是上一次find结束的位置直到走到了end这个是非常易错的地方一定要小心
三、相关题目推荐
26.删除排序数组中的重复项 283.移动零 844.比较含退格的字符串 977.有序数组的平方
