专栏首页InvQ的专栏快慢指针删除数组目标值

快慢指针删除数组目标值

problem

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

solution

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

最后由

删除2后

变为了

返回i+1,就是慢指针的下标。

class Solution {
    public int removeElement(int[] nums, int val) {
          int len = nums.length;
          if (len == 0) {
              return 0;
          }
          int i = 0;
          for (int j = 0; j < nums.length; ++j) {
                //如果等于目标值,则删除
                if (nums[j] == val) {
                    continue;
                }
                // 不等于目标值时,则赋值给num[i],并移动i指针+1
                nums[i++] = nums[j];
          }
          return i;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我们为什么需要MapReduce?

    我们为什么不能使用数据库来对大量磁盘上的大规模数据进行批量分析呢?我们为什么要使用MapReduce? 这些问题的答案来自磁盘的另一个发展趋势: 寻...

    MickyInvQ
  • 数据库基础知识总结

    转载请注明:http://blog.csdn.net/uniquewonderq

    MickyInvQ
  • Windows 下Oracle数据库安装以及Oracle SQL Developer(图文详解)

    转载请注明:http://blog.csdn.net/uniquewonderq

    MickyInvQ
  • Python|“双指针法”解删除数组重复项问题

    Python算法题目中,掌握一定的方法和技巧或者说是了解基础解题规律,能够在解决更多复杂问题的过程中思路更清晰,算法更简单易懂。接下来用一个leetcode题目...

    算法与编程之美
  • LeetCode题目26:删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    二环宇少
  • LeetCode 27. 移除元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

    freesan44
  • 算法养成记:移除元素

    Given an array nums and a value val, remove all instances of that value in-place...

    三哥
  • 移除元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

    _kyle
  • 漫画:原地删除类题型详解(二次修订版)

    题目27:给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    程序员小浩
  • LeetCode题目27:移出元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

    二环宇少

扫码关注云+社区

领取腾讯云代金券