LeetCode第283题解法与思考

第283题的要求如下：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

题目的难点在于，不能使用额外的内存空间，必须在原数组上操作。

我想到的常规解法有如下三种，但都不是非常满意，具体如下：

方法一、轮询+remove操作

#1: 常规方法，轮询值为0的元素，执行remove操作，并记录操作次数，最后按照删除次数将0添加到列表。用时180ms
def moveZeroes1(nums):
    cts = 0
    i = 0
    while (i < len(nums)):
        if (nums[i] == 0):
            nums.remove(0)
            cts += 1
            i = (i-1) if i>=1 else 0
        else:
            i += 1

    while (cts != 0):
        nums.append(0)
        cts -= 1

    return nums

方法二、暴力remove法

#2: 直接使用remove操作，记录remove次数，发生异常时break，最后按照remove次数将0添加到列表。耗时164ms
def moveZeroes2(nums):
    j = 0
    for i in range(len(nums)):
        try:
            nums.remove(0)
            j += 1
        except ValueError:
            break

    while (j != 0):
        nums.append(0)
        j -= 1

    return nums

方法三、冒泡排序法

#3: 按照元素0存在的次数进行单次冒泡排序。耗时1604ms
def moveZeroes3(nums):
    for k in range(nums.count(0)):
        for i in range(len(nums)-1):
            j = i + 1
            if (nums[i] == 0):
                nums[i], nums[j] = nums[j], nums[i]

    return nums

以上三种方法，虽然都满足要求，也都通过了，但效率都不高，特别是第三种，耗时更是长达1604ms，几乎快要timeout了。前面两种虽然好一些，但是都使用了remove方法，感觉也不是太好，但没办法，自己思维打不开，想不到更好的，直到看见了肖哥的如下解法，我才豁然开朗：

#4: 肖哥的方法，遍历列表，将非零的元素从0位置开始覆盖，剩余位置用0来覆盖. 44ms,效率非常高！！
def moveZeroes4(nums):
    none_zero_item = 0
    for each in nums:
        if (each != 0):
            nums[none_zero_item] = each
            none_zero_item += 1

    for i in range(none_zero_item, len(nums)):
        nums[i] = 0

    return nums

不得不佩服肖哥开阔的思维啊！

记录下来，也分享给大家，然后继续努力！

Github上完整的代码链接如下：

Fighting！！！