今天做了一道leetcode小题，题目叫Move Zeros，地址在这里leetcode: Move Zeros。
题目很简单（我就是在挑简单的题找自信），感觉是一个使用复杂度分析的好例子，简单易懂。我们一步步来，先来看一下题目。
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上提交后的结果如下：
可以看到全部的“testcase”都通过了，但执行效率只打败了约3%的“Python Submission”。显然，这个算法的复杂度偏高了，还有更好的方法。
