LeetCode27. 移除元素，array

1. 题目描述

 

题目来源：https://leetcode-cn.com/problems/remove-element/
 

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

2. 题解 2.1 解题思路

（1）从后向前遍历，pop；若是从前向后遍历，则当前的index与处理之后的array的index不一致；

（2）时间复杂度：

2.2 代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        for i in range(len(nums)-1, -1,-1):
            if nums[i] == val:
                nums.pop(i)

        return len(nums), nums

结果：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

3. Python中函数参数传递的坑

首先进行测试1和测试2

测试1. 函数内部直接修改可变参数

在上面的代码中，定义的nums和n直接传递给函数，我们输出函数调用前和调用后的nums，

if __name__ == '__main__':
    solution = Solution()
    # out = 2
    nums = [1,3,3,6]
    target = 3
    # 运行之前的nums    
    print("nums: ", nums)
    
    # 运行之后的nums
    n1, nums1 = solution.removeElement(nums, target)
    print("nums: ", nums)

 结果如下：

nums:  [1, 3, 3, 6]
nums:  [1, 6]

该结果还是比较直观的，将nums和val传递给函数，函数内部修改nums的值，运行结束之后的nums的值也会改变。

测试2. 函数内部对nums重新赋值给其他变量

下面作修改，不直接改变nums的值，而是将nums的值赋值给nums1，看函数调用前后nums是否一致

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        nums1 = nums
        val1 = val
        for i in range(len(nums1)-1, -1,-1):
            if nums1[i] == val1:
                nums1.pop(i)

        return len(nums1),nums1

if __name__ == '__main__':
    solution = Solution()
    # out = 2
    nums = [1,3,3,6]
    target = 3
    # 运行之前的nums    
    print("nums: ", nums)
    
    # 运行之后的nums
    n1, nums1 = solution.removeElement(nums, target)
    print("nums: ", nums)

结果如下，

nums:  [1, 3, 3, 6]
nums:  [1, 6]

结果仍然是nums发生了改变。那么这中间发生了什么呢？？？

3. 解释

python中变量为对象，而非类型。对于不可变对象（如常数）来说，一样的数值的变量具有相同地址；对于可变对象（如列表）来说，一样的数据的变量可能具有相同的地址（a=..., b=a，变量间的赋值），也可能具有不同的地址（a=[1, 2, 3] b = [1, 2, 3]， 数据的初始化）。参见https://zhuanlan.zhihu.com/p/458806734。

例如，
 

    a=3
    b=3
    print("不可变对象，具有相同值的变量具有相同地址")
    print("a.id:", id(a))
    print("b.id:", id(b))

    a = 3
    b = a
    print("可变对象，具有相同值的变量可能具有相同地址")
    print("a.id:", id(a))
    print("b.id:", id(b))

    a = [1, 2, 3]
    b = [1, 2, 3]
    print("可变对象，具有相同值的变量可能具有不同地址")
    print("a.id:", id(a))
    print("b.id:", id(b))

结果如下：

不可变对象，具有相同值的变量具有相同地址
a.id: 140734724010304
b.id: 140734724010304
可变对象，具有相同值的变量可能具有相同地址
a.id: 140734724010304
b.id: 140734724010304
可变对象，具有相同值的变量可能具有不同地址
a.id: 2459801309768
b.id: 2459801310280

图解释如下：

 通过上图，可以清晰地理解Python中关于可变对象的指针和不可变对象的指针有很大的不同。由此，也可以得出：Python中函数传递参数如果是不可变对象，那么可以看做传递的值（值的改变只在局部有效，函数内部改变不会影响原来变量a值，除非返回值赋值给原变量a）；传递参数如果是可变对象，那么可以看做传递的地址（指针，全局改变，改变值之后原来变量a也发生改变）。

进行如下测试

def func_1(a):
    a += 1
    return a
def func_2(a):
    a.append(0)
    return a

if __name__ == '__main__':
    print("传递参数为不可变对象，传递的值，且返回变量名≠原变量名")
    a = 1
    print("调用前原变量a：{},\t\tid(a):{}".format(a, id(a)))
    b = func_1(a)
    print("调用后原变量a：{},\t\tid(a):{}".format(a, id(a)))
    print("调用后返回变量b：{},\tid(b):{}".format(b, id(b)))
    print("\n")

    print("传递参数为不可变对象，传递的值，且返回变量名=原变量名")
    a = 1
    print("调用前原变量a：{},\t\t\tid(a):{}".format(a, id(a)))
    a = func_1(a)
    print("调用后将值返回给原变量a：{},\tid(a):{}".format(a, id(a)))
    print("\n")

    a = [1,2,3]
    print("调用前原变量a：{},\t\tid(a):{}".format(a, id(a)))
    b = func_2(a)
    print("调用后原变量a：{},\tid(a):{}".format(a, id(a)))
    print("调用后返回变量b：{},\tid(b):{}".format(b, id(b)))

结果如下：

传递参数为不可变对象，传递的值，且返回变量名≠原变量名
a的地址未发生改变
调用前原变量a：1,		id(a):140734724010240
调用后原变量a：1,		id(a):140734724010240
调用后返回变量b：2,	    id(b):140734724010272        # b=func_1(a)

传递参数为不可变对象，传递的值，且返回变量名=原变量名
a的地址发生改变
调用前原变量a：1,			id(a):140734724010240
调用后将值返回给原变量a：2,	id(a):140734724010272    # a=func_1(a)

传递参数为可变对象，传递的地址
a的地址未发生改变，但是a、b地址相同
调用前原变量a：[1, 2, 3],		id(a):1832981189192
调用后原变量a：[1, 2, 3, 0],	    id(a):1832981189192
调用后返回变量b：[1, 2, 3, 0],	id(b):1832981189192  # b=func_1(a)

 上面的实验能够较为清晰地理解Python中关于函数的参数什么时候本身会改变、什么时候本身不会改变。