数组leetcode27-移除元素-爱代码爱编程
首先我们简要看一下题目描述:
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(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],也会被视作正确答案。
这道题我们有3个思路,一方面可以通过暴力解法解决这个问题,另一方面我们可以通过双指针解决,双指针解法里相向双指针,快慢双指针都可以很好的解答这个题目
暴力解法
思路:通过两层for循环,一层外层for循环遍历数组,寻找等于val值的元素,一层内层for循环实现将后面的元素覆盖在等于val值的元素上面,从而使得数组里元素没有val值,实现对val值的剔除
时空复杂度分析
由于有两层for循环,所以时间复杂度为O(n²)
空间复杂度不看形参只看临时变量,下面我写的代码里面只有傻傻的n,j,都是常数阶,所以是O(1)
c++代码如下
class Solution {
public:
int removeElement(vector& nums,int val){
int n = sizeof(nums);
for(int i = 0;i<n;i++){
if(nums[i]=val){
for(int j =i+1;j<n;j++){
nums[j-1]= nums[j];
}
n--;
i--;//这里需要注意的是i--,因为如果不进行i--的话,会漏掉元素
}
}
return n;
}
};
快慢指针
这里先谈快慢指针是因为这种做法其实就是通过快慢指针两者的存在,从而使得他们在一个for循环下完成了两个for循环的工作,同时也都是通过 覆盖 实现生成新的数组
思路:首先快慢指针都同时指向了数组的第一元素,快指针先遍历,寻找新数组的元素,即等于val值的时候跳过循环,不等于val值的时候便是找到了新数组的值,同时将他赋给慢指针,然后慢指针又移,这里右移其实就是为了保证[0,val)里面都是正确数组元素。然后快指针继续往后走判断,依次从而实现新数组的诞生
优秀讲解视频
https://leetcode.cn/problems/remove-element/solution/kuai-man-zhi-zhen-27-yi-chu-yuan-su-by-h-z9zt/
时空复杂度分析
因为只有一个for循环,所以时间复杂度是O(n)
临时变量也是只有傻傻的slow和fast,常数阶,所以空间复杂度是O(1)
c++代码如下
class Solution{
public:
int removeElement(vector<int>& nums,int val){
//我们先确保数组补为空
if(nums.empty()||nums.size()==0) {
return 0;
}
int slow = 0;
for (int fast = 0;fast<nums.size();fast++) {
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}else
{
continue;
}
}
return slow; //返回的slow便是真正确元素的个数,不信你画图分析
}
};
相向左右指针
思路:左右指针突出的是一头一尾,一左一右,左指针从数组头开始向后遍历,直到第一个等于val值的位置停下,右指针从数组尾向前遍历,直到第一个不等于val值的位置停下,然后交换元素,就是实现将正确元素全部丢到前面去,然后val元素全部丢到数组屁股那里,怎么截取新数组呢,这里刚好左右指针会重合,就是左右指针相遇,相遇的时候即前面都是正确元素,这个时候需要判断两种情况,一是重合时候这个值是否等于指定值,如果是指定值,后续就可以直接返回索引位置,这个时候的索引位置就是正确元素的个数。如果不等于val值的话,就返回索引值+1
时空复杂度分析
代码里面3次while循环,即3n,所以时间复杂度是O(n)
临时变量里面只有right和left两个常数阶,所以空间复杂度是O(1)
c++代码如下
class Solution{
public:
int removeElement(vector<int>& nums, int val)
{
//首先判断一下数组是否为空,数组元素个数为0或者数组empty为真
/*
empty()函数
是用来测试变量是否已经配置。若变量已存在、非空字符串或者非零,则返回 false 值;反之返回 true值。
所以,当字符串的值为0时,也返回true
||是或者 &&是且
*/
if(nums.size()==0||nums.empty()) {
return 0;
}
//定义左右指针且初始化下标
int left =0;int right = nums.size()-1;
//然后跳入while循环,首先是大循环条件,left<right
while(left<right){
while(left<right&&nums[left]!=val){
left++;
}
while(left<right&&nums[right]==val){
right--;
}
//一个简单的交换元素
int temp = nums[left];
nums[left] = nums[right];
nums [right] = temp;
}
//然后判断相遇点这个值是否等于val,如果等于val就直接返回left的值,因为它前面的元素都是有效个数
//如果不是val就需要加一
if(nums[left]==val)
{
return left;
} else{
return left+1;
}
}
};
总结
移除元素虽然是力扣数组里面的简单题,但是作为一个新手去完成这道题也付出了很多时间精力,从一开始的无从下手到后面的探寻不同方法解答该道题,这是一个从无到有的过程。自己坚持做下来并写了博客去记录,最终还是让人挺开心的。现在自己也对通过刷题去掌握数据结构有了信心和方向。现在我们来谈谈这道题目,这道题目是在一个数组里面移除元素,然后返回新数组的元素个数,一谈到移除元素,我们想到的是删除操作,但是奈何数组的存储方式是连续的,它的优势是可以根据下标快速随意访问任何一个位置的元素,但插入好删除就不是那么直接好操作了,所以这里我们想要得到新数组并返回它的元素个数,就应该想到将元素覆盖,将正确元素放在一块,然后通过条件判断截取出新的数组。暴力解法就是简单粗暴,只要能实现目的,不考虑复杂与否,所以既然要覆盖,那就得写第一个for循环遍历,先找到val元素,然后在另一个for循环里面实现将后一位赋值给它,从而依顺序实现慢慢将前面的元素都变成正确的,至于这样子麻烦做都是因为数组它的存储结构是顺序的,所以必须依顺序来,这个时候我们的思维方式不能站在一个上位者的高度去想直接将元素怎么排怎么排,必须以数组结构是顺序的,连续内存存储的这一基点去思考如何实现。emmmm,我好像是个笨蛋,我有点不能捋清楚这个思路了。刚才我是想说内层for循环是要直接从后一位赋值给前一位,而不判断一下,因为要是后一位又是val值的话,又要重复一遍无用功,要是能判断一下跳过那个数就减少了步骤,哦哦,我知道了,要是这样子跳过,就不好实现我们的思路,基于数组是连续存储的,我们必须耐着性子一一遍历一一赋值。所以我们想要换个办法去移除元素的话,可以引用双指针,这样子就有可操作性了,但同时必须也要尊重数组结构的特殊性,即使用了左右指针何快慢指针,数组结构依然是存储且连续的,我们要一步一步来,只是说时间复杂度相比O(n²)少了。快慢指针和左右指针的具体操作和思路也是跟暴力解法差不多的,通过 覆盖和调换位置实现 ,只不过是用来双指针取巧,使时间复杂度降低。好咯,这篇博客就写到这里了。下篇博客我们来手撕LeetCode59 螺旋矩阵Ⅱ,呜,有点子期待,明天就干它!