Lintcode Python之移动零

移动零（Move Zeroes）

题目：

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序。

样例：

给出 nums = [0, 1, 0, 3, 12], 调用函数之后, nums = [1, 3, 12, 0, 0].

注意事项

1.必须在原数组上操作
2.最小化操作数

思路：

由于必须在原数组上操作，要么移动赋值，要么就remove & append方法。

（1）

移动赋值的话，想到双指针首尾靠近遍历，版本一的代码出来了：

def moveZeroes(self, nums):
    # Write your code here
    i, j = 0, len(nums)-1 # 首尾指针
    while i<=j:
        if nums[i]==0:
            while nums[j]!=0:
                nums[i], nums[j] = nums[j], nums[i] #交换值
            else:
                j -= 1
        i += 1

但是这个没有考虑到题目要求的非零元素保持原数组的顺序。Fail

（2）

版本二，直接用list 的 remove&append 方法
代码：

def moveZeroes(self, nums):
    # Write your code here
    N = nums.count(0)
    for i in range(N):
        nums.remove(0)
        nums.append(0)
        i += 1

（3）

还有其他高手也写出更短的代码：

def moveZeroes(self, nums):
    # Write your code here
    for num in nums:
        if num == 0:
            nums.remove(0)
            nums.append(0)

测试

如果不考虑非零元素保持原数组的顺序这一条件，版本一的代码灰常快。
来看看以下比较

from timeit import timeit # 计时器

"""版本二 remove & append方法"""
def func1():
    num = nums.count(0)
    for i in range(num):
        nums.remove(0)
        nums.append(0)
        i += 1

"""版本二 remove & append方法 最短代码"""                       
def func2():
    for i in nums:
        if i == 0:
            nums.remove(0)
            nums.append(0)

""" 版本一  代码"""
def func3():
    i, j = 0, len(nums)-1
    while i <= j:
        if nums[i] == 0:
            while nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                j -= 1
        i += 1

测试过程：

import random

f1, f2, f3, f4, f5 = [[]] * 5
for i in range(30):
    nums = [random.randint(0, i) for j in range(600)] #每次随机产生600个0~i的数字
    f1.append(timeit(func1, number=100)) # 每个函数运行100次
    f2.append(timeit(func2, number=100))
    f3.append(timeit(func3, number=100))
    f4.append(f1[i]-f2[i]) # 与最短代码版本的运行时间差值
    f5.append(f3[i]-f2[i]) # 与最短代码版本的运行时间差值
print(sum(f1)/30, sum(f2)/30, sum(f3)/30, sum(f4)/sum(f2), sum(f5)/sum(f2), sep="||")
# 输出每个函数的平均运行时间，运行时间差值占比

运行结果如下：
0.06555597698982941||0.06603924254365362||0.011495922738686205||-0.0073178542819409935||-0.8259228559278659
可以看到，不考虑非零元素保持原数组的顺序这一条件的话，最初版本的代码比其他两个快了80%左右；
而代码二和代码三（最短的那个代码）差别不大。这个测试对于代码二和代码三还是比较粗糙的。
再附上详细一点的测试代码：

L = []
random.seed(42)
for j in range(100): # 重复100次
    f1 = []
    f2 = []
    f3 = []
    for i in range(1):
        nums = [random.randint(0, i+3) for j in range(500)]
        f2.append(timeit(func2, number=1000))
        f1.append(timeit(func1, number=1000))
        f3.append(f1[i]-f2[i])
    L.append(sum(f3))

画图查看结果

import matplotlib.pyplot as plt
plt.figure(figsize=(18, 5))
plt.subplot(121)
plt.hist(L)
plt.subplot(122)
plt.plot(range(100), L)
plt.show()

print(sum(L)/len(L)) # 代码二比代码三运行总时长短s秒
#打印出>>>-0.0008692948313910165

总结：在0的个数占比较少时代码二速度优于代码三几个百分点，反之代码三优于代码二。波动性这么大的原因之一应该就是0的位置不确定，越靠后，代码二运行时长就长一点点。但总的来说，交叉点大概在0 的个数占比为40%左右。
分析思路仅供参考–>逃<–