数组:啥?要移除我的元素

源码共读

共 553字,需浏览 2分钟

 ·

2021-01-28 18:18


Python实战社群

Java实战社群

长按识别下方二维码,按需求添加

扫码关注添加客服

进Python社群▲

扫码关注添加客服

进Java社群


作者丨tan45du
来源丨袁厨的算法小屋

题目描述

题目

暴力解法

暴力题解

做题思路

该题目也算是简单题目,适合新手来做,然后大家也不要看不起暴力解法,我们可以先写出暴力解法,然后再思考其他方法,这对于我们的编码能力有很大的帮助。我们来解析一下这个题目的做题思路,他的含义就是让我们删除掉数组中的元素,然后将数组后面的元素跟上来。最后返回删除掉元素的数组长度即可。比如数组长度为10,里面有2个目标值,我们最后返回的长度 为8,但是返回的8个元素,需要排在数组的最前面。那么暴力解法的话则就需要两个for循环,一个用来找到删除,另一个用来更新数组。总体思路就是这样的,后面的会不断往前覆盖。暴力解法也是不超时的,实现也不算太简单主要需要注意两个地方。

(1)需要先定义变量len获取数组长度,因为后面我们的返回的数组长度是改变的,所以不可以用nums.length作为上界

(2)我们每找到一个需要删除的值的时候,需要i--,防止出现多个需要删除的值在一起的情况,然后漏删。

题目代码

代码也比较简单

class Solution {
    public int removeElement(int[] nums, int val) {
        //特殊情况需要注意
        if(nums.length == 0){
            return 0;
        }
        //获取数组长度,作为for循环的上界
        int len = nums.length;
        for(int i = 0; i < len ; i++){
            //找到需要删除的元素
            if(nums[i]==val){ 
               //覆盖需要删除的元素               
                for(int j = i+1 ; j < len ; j++){
                    nums[j-1] = nums[j];
                }
                //保留当前索引,防止漏删
                i--;
                //缩小需要返回的长度
                len--;                
            }
        }
        return len;
    }
}

快慢指针

快慢指针

做题思路

快慢指针的做法比较有趣,只需要一个for循环即可解决,时间复杂度为O(n),总体思路就是有两个指针,前面一个后面一个,前面的用于搜索需要删除的值,当遇到需要删除的值时,前指针直接跳过,后面的指针不动,当遇到正常值时,两个指针都进行移动,并修改慢指针的值。最后只需输出慢指针的索引即可。

题目代码

代码也比较简单大家可以参考一下

class Solution {
    public int removeElement(int[] nums, int val) {
    //特殊情况
      if(nums==null){
          return 0;
      }     
      int j = 0;//慢指针,i代表快指针
      for(int i = 0;i         //正常情况直接赋值给i          
          if(nums[i]!=val){
              nums[j]=nums[i];
              j++;
          }
          //如果为需要删除的值时,则快指针移动,慢指针不动。
      }
       return j;
    }
}

总结

总的来说这个题目还算不错,算是打开了双指针的大门,后面还会有很多双指针的题目,大家快加我好友我拉你进群,咱们一起刷题吧。


扫描二维码

加我好友一起群内打卡

程序员爱做饭

 


作者:LeetCode 链接:https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

程序员专栏
 扫码关注填加客服 
长按识别下方二维码进群

近期精彩内容推荐:  

 再见,戴威!再见,小黄车!

 别瞎学了,这几门语言要被淘汰了!

 再见 Win10!下一代操作系统来了。。

 墙裂建议收藏,100道Python练手题目




在看点这里好文分享给更多人↓↓

浏览 19
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报