这是我的第一篇博客，可能内容不是特别高深😂，也请大家多多包容😊
欢迎大家指正我的不足😊
欢迎大家指正我的不足😊
欢迎大家指正我的不足😊
其实刚开始我是不愿意写博客的，但是后来我感觉写博客不仅可以帮助他人，也能使自己复习，因为我写的题目博客都是我容易忘记的😉
回归正题🤐
⭐这个题的题意刚开始没有读懂，以为O(1)是时间复杂度，但其实是空间复杂度🤣
🍔因为仅使用O(1)的空间，所以不能额外开辟一个数组
然后，我看了Carl哥的分享，有多种方法，下面我来用我的语言（不是编程语言）讲一下😊
这是Carl哥的分享 代码随想录 (programmercarl.com)
好！
⭐方法1
暴力算法——直接把数组中的元素前移（后面的元素覆盖前面的元素）
要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& 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--;
size--;
}
}
return size;//题目要求返回新数组的长度
//可以理解为返回一个长度，然后系统会根据这个长度去遍历这个数组
}
};我发现，最好不要省略花括号（以防万一😂）
这里面有个容易出错的地方，就是
一定要首先用size=nums.size()，然后后面需要用nums.size()的地方用size代替
因为
自增自减运算符只能用于变量 不能用于常量和表达式nums.size()是表达式
还有一些值得注意的地方(I think)，请看图片
⭐方法2
双指针算法——可以把二维循环变成一维循环
相同方向的指针
时间复杂度：O(n^2）
空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int t=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=val)
nums[t++]=nums[i];//这里面不能重新开一个数组来存a[t++]=nums[i]
//我感觉应该是因为返回的t是nums[]的
//nums[t++]=nums[i]后nums里面的数已经改变了
//如果重新看一个数组不能达到这样的效果
}
return t;
}
};
相反方向的指针
时间复杂度：O(n^2）
空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l=0,r=nums.size()-1;
while(l<=r)
{
while(l<=r&&nums[l]!=val)//我感觉是因为数组下标是从左向右排列的，所以是！=
++l;
while(l<=r&&nums[r]==val)
--r;
if(l<r)//这个地方 是< 而不是<=
nums[l++]=nums[r--];
}
return l;
}
};🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥🚥
第二天听y总的课，发现一个用双指针写的剑指offer的题
妙😍（好像这个模板像快排）
🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈
十几天后，看到一个题，看上去十分简单；但是第一想法就是用两个for循环
其实也可以用双指针来写
由于两个数组都是有序的，所以可以使用双指针分别指向两个数组遍历，如果当前两个数字不相同，则向后移动较小数字的指针。
时间复杂度为 O(min(n,m))
class Solution {
public:
int getCommon(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j])
return nums1[i];
if (nums1[i] < nums2[j]) i++;
else j++;
}
return -1;
}
};
🎆🎆🎆🎆🎆🎆🎆🎆🎆🎆
That’s all,thank you!😉
欢迎大家指正我的不足😊
欢迎大家指正我的不足😊
欢迎大家指正我的不足😊
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/131441.html
