不使用额外内存时在列表中删除指定元素

Question: 不使用额外内存时在列表中删除指定元素

👉LeetCode链接👈

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 in place with constant memory.

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

给定一个数组和值，在不生成新列表（不定义新的列表）的情况下，删除在这个列表中的这个指定的值，元素中的顺序可以被改变

Example

1
2
3
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Answer

1
2
3
4
5
6
7
8
9
10
11
12
def removeElement(nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """
    j = 0
    for i in range(len(nums)):
        if nums[i-j] == val:
            nums.remove(nums[i-j])
            j += 1
    return nums

Finally

问题中声明不让为一个新的列表创建新的内存空间，也就是不让创建一个新的列表，但是没限制不可以创建一个新的变量，那么我们就可以创建一个新的变量用来记录删除元素的次数，因为再循环列表时直接删除元素，会导致列表长度发生改变，导致最后发生错误，但是增加一个变量记录删除元素的次数的话就可以知道删除几次了，再删除的时候就可以把长度补回来，也就不会出现 out of range 的错误了