题目描述

题目要求从数组中删除指定值的元素，并返回新数组的长度。元素的顺序可以被改变，也不关心最终的数组长度。（不用做数组切分slice操作，把最后留下的元素放在前面即可）。

本题特别像：26题

我的解法——记录应前移的位数（双指针+前移）

用一个额外空间记录当前元素应该向前移的位数，这个数now随着数组往后遍历不断变化：
- 若前一个元素和要删除的元素val相等：now++
- 若前一个元素和要删除的元素val不等：now不变
n的复杂度。
结果：beat 25.28%

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        now = 0
        nums.append(-val) # 注意这里，要append一个元素！！！否则最后一个元素可能会出问题！！！
        for i in range(1,len(nums)):
            if(nums[i - 1] == val):
                now += 1
            nums[i - now] = nums[i]
        return len(nums) - now - 1  # 由于前面append了一个元素，这里需要减1

简便解法——双指针+交换位置

**最好的方法！！ **
用于要删除的数val很少时。比如：nums=[4,1,2,3,5],val=4时没必要一个数一个数地往前移动（由于题目说数的顺序可以颠倒）。
思路：当遇到nums[i]=val时，交换当前元素和最后一个元素，并将后面的指针前移一位。交换的最后一个元素可能是想要移除的值。但在下一次迭代中，仍然会检查这个元素。
一层循环，n的复杂度，移动数字的次数为需要剔除的数的一个子集。
beat 74.94%

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0
        j = len(nums)
        while(i < j):
            if(nums[i] == val):
                nums[i] = nums[j - 1]
                j -= 1
            else:
                i += 1
        return j

参考答案

https://leetcode.com/problems/remove-element/solution/