Move Zeros

Given an arraynums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, givennums = [0, 1, 0, 3, 12], after calling your function,nums should be[1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

题目并不复杂，就是把一个数组里边儿的零都移到末尾。唯一需要注意的是，它要求“in-place”--就地解决，不能使用额外的存储空间，比如拷贝数组的操作是不允许的。

看完题目以后先思考几分钟吧。下面几节，我会描述一下我的思考过程。

原子操作

题目要求“in-place”的解决，那么我们这时候可以做哪些操作呢？

赋值
修改列表（数组）元素的值是可以的，这是对现有内存的操作，不会使用额外的空间。
交换
赋值可以，那么交换可以吗？我们常用的交换是三次赋值，使用一块临时空间，像这样：
```
 tmp = a[i]
 a[i] = a[j]
 a[j] = tmp
```
还有不使用额外空间的技巧，像这样：
```
  a[i] = a[i] + a[j]
  a[j] = a[i] - a[j]
  a[i] = a[i] - a[j]
```
所以，只要赋值操作可以做，交换就可以。

你还能想到其它的操作么？想到了一定告诉我，反正我没想到。

题目的任务现在可以理解成这样：通过赋值或者交换的手段，在不破坏非零元素顺序的情况下，把所有的零元素移到列表的末尾。

O(n^2)

我首先想到的算法是基于交换的。以题目中给出的示例为例：

    [0, 1, 0, 3, 12] => [1, 3, 12, 0, 0]

观察上面的例子，我们发现两点事实：

终结状态是确定的，一个初始状态必然对应一个确定的终结状态；
由于元素的值是不可变的，所以终结状态和初始状态的差别只是元素位置的差别。

根据以上事实，从终结状态出发可以推理出，当一个零元素的位置不正确的时候，必然占据了另一个非零元素的正确位置。

    [0, 1, 0, 3, 12] => [1, 3, 12, 0, 0] # 第一个元素“0”，占据了元素“1”的位置

如果我们能够找到那个非零元素，让两者交换位置，就可以让非零元素进入正确的位置。

    [0, 1, 0, 3, 12] => [1, 0, 0, 3, 12] # 一次交换，元素“1”进入正确的位置

由于零元素的位置不需要精确（零元素的排列顺序无意义），所以只要保证所有的非零元素的位置正确，我们就得到正确的结果了，如下

    [0, 1, 0, 3, 12] => [1, 0, 0, 3, 12] # 一次交换，元素“1”进入正确的位置
    [1, 0, 0, 3, 12] => [1, 3, 0, 0, 12] # 二次交换，元素“3”进入正确的位置
    [1, 3, 0, 0, 12] => [1, 3, 12, 0, 0] # 三次交换，元素“12”进入正确的位置

最后回答一个问题，零元素占据了那个非零元素的位置？因为非零元素的有序性，显然是从左往右最靠近它的非零元素。

根据以上分析，我们构建以下算法：

    def moveNums(nums):
        # 遍历列表
        for i in range(len(nums)):
            # 如果发现零元素，就向右寻找最靠近它的非零元素，交换两者位置
            if nums[i] == 0:
                for j in range(i+1, len(nums)):
                    if nums[j] != 0:
                        nums[i] = nums[j]
                        nums[j] = 0 
                        break

        return nums

这个算法的复杂度很好分析，两个"for-loop"的结构，显然是O(n^2)的。在leetcode上提交后的结果如下：