上海市建设项目施工审图网站,市场营销的主要应用领域,内容不相关的网站做301重定向,梧州做网站⭐今日份题目
给你一个数组 nums 和一个值 val#xff0c;你需要 原地 移除所有数值等于 val 的元素#xff0c;并返回移除后数组的新长度。
不要使用额外的数组空间#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中…⭐今日份题目
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数但输出的答案是数组呢?
请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说不对实参作任何拷贝
int len removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i 0; i len; i) {print(nums[i]);
}
示例1
输入nums [3,2,2,3], val 3
输出2, nums [2,2]
解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。
示例2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,3,0,4]
解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示 0 nums.length 100 0 nums[i] 50 0 val 100
⭐题目思路
这里还是提取一下题目的特征点 原地移除
原地移除考虑用vector作为STL库中一员的erase函数该函数可以在原数组中直接删除对应位置的元素基本语法
vector.erase(vector.begin()i)//表示删除掉数组中下标为i的元素
这样的好处是无需额外的变量空间但问题也随之产生⭐原地删除后vector中的元素的下标会对应的发生变化vector的长度也对应发生变化那么就需要额外考虑下标的处理问题。大致有以下几个方面 删除掉下标为i的元素后新一轮的for循环中下标为i的元素其实是还未被遍历过的所以需要i--来遍历这个元素。
class Solution
{
public:int removeElement(vectorint nums, int val) {for(int i0;inums.size();i){if(nums[i]val) {nums.erase(nums.begin()i);i--;}}return nums.size();}
};
该方法的执行用时和内存消耗如下图所示 仍有进步的空间。
在之前调试的时候我发现了一个很奇怪的现象我在return前加了一句代码
if(nums.size()1nums[0]val) return 0;
然后运行用时就变为了0ms然后内存消耗反而增大了。这里我其实不是很理解欢迎大佬们帮我解答一下评论区见~
这道题也是有点典型的STL风感兴趣的初学朋友可以去看一下~
⭐vector补充知识
vector还有一些常用的函数这里补充一下
//定义一个vector类型为int
vectorint a;
//定义一个int型长度为10的vector
vectorint b(10);
//定义一个int型长度为10初始值均为3的vector
vectorint c(10,3);//将vector中的最后一个元素改成4
a.back()4;
⭐(这个符号表示时间复杂度) O(1)
//清空vector
a.clear();
⭐ O(n)
//在vector末尾增加一个3
a.push_back(3);
⭐ O(1)
//删除末尾元素
a.pop_back();
⭐ O(1)//该部分比较少用时间复杂度都为O(该变量)
//截取长度为11缺的补0不缺就直接截取
a.resize(11);
//截取长度为11缺的补5
a.resize(11,5);//判断元素个数
a.size();
⭐ O(1)
//判断vector中是否无元素了没有了就返回true
a.empty();
⭐ O(1)//vector作为迭代器
a.begin();//返回a的第一个元素的位置
a.end();//返回a的最后一个元素的下一个位置
sort(a.begin(),a.end());//插入删除慎用因为时间复杂度为O(n)有点慢
//在下标为2从0开始的位置插入0元素
a.insert(a.begin()2,0);
//删除下标为2的元素
a.erase(a.begin()2);
//删除区间左闭右开
a.erase(a.begin()1,a.begin()4);
⭐一切会让vector长度变化的操作都可能让之前的迭代器失效这也是该题目我们需要额外考虑的地方。
这里如果有不懂的地方欢迎评论区留言⭐~
⭐代码
class Solution
{
public:int removeElement(vectorint nums, int val) {for(int i0;inums.size();i){if(nums[i]val) {nums.erase(nums.begin()i);i--;}}if(nums.size()1nums[0]val) return 0;return nums.size();}
};
提交结果 我的代码还有待改进欢迎大家提供更高效的代码如果过后有更优化的思路我还会继续更新的大家评论区见
点赞收藏不迷路⭐~
