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

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

Example: 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.

直观解法是扫描数组，当遇到value时，将value右边所有元素向左移一格，直接到扫完所有数字。但这种解法在移动操作上的消耗是很大的，最差情况时间复杂度为O(n^2)。

由于数组元素顺序不需要维持，可以采取当遇到value时，用顺组尾部元素来填充。同样是双指针的技巧：left指针扫描数组，right指针表示当前数组的尾端。

(1) A[left]=value时，A[left] = A[right], right--，但不能left++，因为也可能A[right]=value

(2) A[left]!=value时，left++

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        """
        #当把长度改变以后，数据再次for loop的时候就乱了，下面的是错误的：
        for num in nums:
            if num == val:
                nums.remove(num)
        return len(nums)
        """
        start, end = 0, len(nums) - 1
        while start <= end:
            if nums[start] == val:
                nums[start], end = nums[end], end - 1
            else:
                start +=1
        return start

注意用while loop的条件