移动零

发表于 更新于 分类于 阅读次数：

题目

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

示例:

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

说明:

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

Python解：

新建一个索引，遍历数组，将非零的数移到新索引，零数就移到后面（直接赋值）

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def moveZeroes(self, nums):
        j = 0 
        for i in range(len(nums)):
            if nums[i] != 0 :
                nums[j] = nums[i] #交换位置
                if i != j: #避免修改同一位置
                    nums[i] = 0
                j += 1 #更新索引位置（当前j位置已被非零数占用）
        return nums

耗时:24ms

简化：

1
2
3
4
5
6
7
8
class Solution(object):
    def moveZeroes(self, nums):
        j = 0 
        for i in range(len(nums)):
            if nums[i] != 0 :
                nums[j],nums[i] = nums[i],nums[j] #位置交换，等价于：z=j, j=i, i=z
                j += 1
        return nums

耗时：32ms

最优解：使用xrange

1
2
3
4
5
6
7
8
class Solution(object):
    def moveZeroes(self, nums):
        j = 0 
        for i in xrange(len(nums)):
            if nums[i] != 0 :
                nums[j],nums[i] = nums[i],nums[j]
                j += 1
        return nums

耗时：28ms

xrange与range区别：

1.range和xrange都是在循环中使用，输出结果一样。
2.range返回的是一个list对象，而xrange返回的是一个生成器对象(xrange object)。
3.xrange则不会直接生成一个list，而是每次调用返回其中的一个值，内存空间使用极少，因而性能非常好。