283.移动零 关于列表list与remove原理*****

题目：

　　给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

　　注意，该题目要求不开辟行的数组空间，在原数据上进行操作。

　　示例:

　　输入: 
　　输出: [0,1,0,3,12][1,3,12,0,0]

　　说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

自我解答：

　　思路1：如同冒泡算法那样，用两个for循环进行遍历，将0依次移动到列表最后面。

　　缺点：复杂度太高，n^n，上传答案时会报错。

　　思路2：for循环遍历数组，当该数为0时，remove移除该数，

　　　　在这里有两个python知识点。

　　原本，我是希望先把所有的0删除后，再往后面添加同样数量的0，但是，发现删不掉0的情况

list1 = [0,2,0,0,8,0,8,0,1]
class Solution2:
    def moveZeroes(self, nums):
        for i in nums:
            if i ==0:
                nums.remove(i)
                # nums.append(0)
        print(nums)

s = Solution2()
s.moveZeroes(list1)
#[2, 8, 8, 0, 1]

　　百度了一番发现了其中的奥秘：

　　for循环原理

　　python中for循环是遍历所有nums下标，然后根据下标遍历列表。

　　当列表边遍历边删除的时候，会出现漏遍历的情况，当列表中的数字被删除时，后面的数字会跟上，他们的下标也会跟着改变，如

list1=[1,2,3,4,5,6]
for i in list1:
    remove(i)
#[2,4,6]

　　因为删除了1，所以2代替了原来1的位置，for循环就会寻找现在列表中的2位置是谁，很显然2是数字3.

　　但是又有一个问题，难道在遍历了6之后还有3个下标没有遍历会怎么处理呢。

　　这就涉及到for循环的内部原理，其中有__next__方法就是获取下一个元素，当获取不到时就会报错，然后内部处理异常，停止取值。

　　remove原理

　　但光是这样的话，上述代码最后执行的结果不就是[2,0,8,8,0,1]吗。

　　原来remove的删除原因是删除当前列表中第一个匹配的值，所以当遍历到后面的0时会删除前面跳过的0，但是遍历到的0总是比较少的，所以最后总会漏掉1到2个。

　　解决方法：

　　1.这个方法不是很完美，因为方法不变，只是边删除0边在后面添加0，这就使得原先没有遍历结束的下标全部遍历，所以不妨换一个角度想。

　　我们每遍历到一个0就获得删除一个0的机会（remove），每删除一个0就会添加一个0，所以列表总长度不变，最后原先列表遍历结束后，就会遍历添加进去的0，直到遍历结束。

　　或者理解为保证列表长度不变的情况下，尽可能的删掉队列中所有的0，那这些0到哪里去了呢，显然就是append的哪些：

list1 = [0,2,0,0,8,0,8,0,1]
class Solution2:
    def moveZeroes(self, nums):
        for i in nums:
            if i ==0:
                nums.remove(i)
                nums.append(0)
        print(nums)
#[2, 8, 8, 1, 0, 0, 0, 0, 0]

　　2，从后往遍历。

　　这种方法适用于任何边循环边改变列表元素的问题，使用切片中默认值的方式：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        for i in nums[::-1]:
            if i==0:
                nums.remove(i)
                nums.append(0)

　　添加的0和剔除的0在总列表的最后，不会影响for循环中即将遍历的值.

官方解答：

　　这个题目的标签是数组与双指针。可以这么做：

　　定义一个长指针和一个短指针。

　　长指针用来判断列表中的0元素直到最后，短指针则用来记录非0的值到列表中。

　　最后再在短指针的最后将所有的值改成0，实现该功能。

list1 = [0,2,0,0,8,0,8,0,1]
class Solution:
    def moveZeroes(self, nums):
        long_t = 0
        short_t = 0
        while long_t < len(nums):
            if nums[long_t]!=0:
                nums[short_t] = nums[long_t]
                long_t +=1
                short_t +=1
            else:
                long_t +=1
        while short_t <len(nums):
            nums[short_t] = 0
            short_t += 1
        print(nums)

#[2, 8, 8, 1, 0, 0, 0, 0, 0]

　　python中实现指向数组的指针都可以使用这种方法，这种方法在执行时间的角度来讲也比较合理。

 

 

 

 

 

 

 

示例:

输入: 
输出: [0,1,0,3,12][1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。