27.移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 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]，也会被视作正确答案。

题目链接

思路

双指针
设置两个指针，左指针left，右指针right，左指针left指向待插入不等于val的值，right指针遍历寻找不等于val的值，如果找到，就将right指针指向的值复制到left指针指向的位置，
然后left指针后移到下一个待插入位置，right指针继续后移寻找下一个不等于val的值，依次类推。
双指针优化
如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。
当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。
这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

代码
class Solution(object):
```
 def removeElement(self, nums, val):
     """
     双指针
     :type nums: List[int]
     :type val: int
     :rtype: int
     """
     left = 0
     right = 0
     while right < len(nums):
         if nums[right] != val:
             nums[left] = nums[right]
             left += 1
         right += 1
     return left
 
 def removeElement1(self, nums, val):
     """双指针优化"""
     left = 0
     right = len(nums)
     while left < right:
         if nums[left] == val:
             nums[left] = nums[right - 1]
             right -= 1
         else:
             left += 1
     
     return left
```
if name == “main“:
```
 slt = Solution()
 result = slt.removeElement([3, 2, 2, 3], 3)
 print(result)
```

victory的博客

leetcode | 27.移除元素

27.移除元素

题目描述

思路

代码