27. Remove Element

题目描述：

Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.

题目翻译

给定一个数组和一个值，就地删除数组中和该值相同的所有元素并返回新的长度。

不要创建其他数组分配额外的空间，你必须通过O（1）空间复杂度就地修改输入数组来实现这一点。

元素的顺序可以改变。只要返回了新的长度，数组中是否存在超过这个索引的元素无所谓（即数组中高索引元素可以不删除）。

示例1：

给定的数组 = [3,2,2,3], 值 = 3,
你的函数应该返回长度=2，数组修改后前两个元素为2

解题方案

标签： Two Pointers

思路：

• 本题需要维护两个数组指针i和j，从数组0元素遍历至数组最后一个元素。若在数组中发现和给的val值相同的元素，则将数组后面和val值不同的元素前移覆盖这个元素。

• 算法复杂度O(n)。

代码：

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0
        j = 0
        while j < len(nums):
            if nums[j] == val:  # 数组内的值和要删除的元素值相同
                j += 1
            else:
                if i != j:  # 将数组后边和所给元素不相同的元素前移
                    nums[i] = nums[j]
                i += 1
                j += 1
        del nums[i:len(nums)]  # 删除多余元素
        return len(nums)

参考资料

• http://blog.csdn.net/dongrongyu/article/details/78463400
• 作者：董荣堉