今天做了一道leetcode小題蕴侧，題目叫Move Zeros府蛇，地址在這里leetcode: Move Zeros腺怯。
題目很簡(jiǎn)單（我就是在挑簡(jiǎn)單的題找自信），感覺是一個(gè)使用復(fù)雜度分析的好例子诽俯，簡(jiǎn)單易懂妇菱。我們一步步來，先來看一下題目暴区。
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.
題目并不復(fù)雜闯团，就是把一個(gè)數(shù)組里邊兒的零都移到末尾。唯一需要注意的是颜启，它要求“in-place”--就地解決偷俭，不能使用額外的存儲(chǔ)空間，比如拷貝數(shù)組的操作是不允許的缰盏。
看完題目以后先思考幾分鐘吧涌萤。下面幾節(jié)淹遵，我會(huì)描述一下我的思考過程。
原子操作
題目要求“in-place”的解決负溪，那么我們這時(shí)候可以做哪些操作呢透揣？
賦值
修改列表（數(shù)組）元素的值是可以的，這是對(duì)現(xiàn)有內(nèi)存的操作川抡，不會(huì)使用額外的空間辐真。-
交換
賦值可以，那么交換可以嗎崖堤？我們常用的交換是三次賦值侍咱，使用一塊臨時(shí)空間，像這樣：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]所以楔脯，只要賦值操作可以做，交換就可以胯甩。
你還能想到其它的操作么昧廷？想到了一定告訴我，反正我沒想到偎箫。
題目的任務(wù)現(xiàn)在可以理解成這樣：通過賦值或者交換的手段木柬，在不破壞非零元素順序的情況下，把所有的零元素移到列表的末尾淹办。
O(n^2)
我首先想到的算法是基于交換的眉枕。以題目中給出的示例為例：
[0, 1, 0, 3, 12] => [1, 3, 12, 0, 0]
觀察上面的例子，我們發(fā)現(xiàn)兩點(diǎn)事實(shí)：
- 終結(jié)狀態(tài)是確定的娇唯，一個(gè)初始狀態(tài)必然對(duì)應(yīng)一個(gè)確定的終結(jié)狀態(tài)齐遵；
- 由于元素的值是不可變的，所以終結(jié)狀態(tài)和初始狀態(tài)的差別只是元素位置的差別塔插。
根據(jù)以上事實(shí)，從終結(jié)狀態(tài)出發(fā)可以推理出拓哟，當(dāng)一個(gè)零元素的位置不正確的時(shí)候想许，必然占據(jù)了另一個(gè)非零元素的正確位置。
[0, 1, 0, 3, 12] => [1, 3, 12, 0, 0] # 第一個(gè)元素“0”断序，占據(jù)了元素“1”的位置
如果我們能夠找到那個(gè)非零元素流纹，讓兩者交換位置，就可以讓非零元素進(jìn)入正確的位置违诗。
[0, 1, 0, 3, 12] => [1, 0, 0, 3, 12] # 一次交換漱凝，元素“1”進(jìn)入正確的位置
由于零元素的位置不需要精確（零元素的排列順序無意義），所以只要保證所有的非零元素的位置正確诸迟，我們就得到正確的結(jié)果了茸炒，如下
[0, 1, 0, 3, 12] => [1, 0, 0, 3, 12] # 一次交換愕乎，元素“1”進(jìn)入正確的位置
[1, 0, 0, 3, 12] => [1, 3, 0, 0, 12] # 二次交換，元素“3”進(jìn)入正確的位置
[1, 3, 0, 0, 12] => [1, 3, 12, 0, 0] # 三次交換壁公，元素“12”進(jìn)入正確的位置
最后回答一個(gè)問題感论，零元素占據(jù)了那個(gè)非零元素的位置？因?yàn)榉橇阍氐挠行蛐晕刹幔@然是從左往右最靠近它的非零元素比肄。
根據(jù)以上分析，我們構(gòu)建以下算法：
def moveNums(nums):
# 遍歷列表
for i in range(len(nums)):
# 如果發(fā)現(xiàn)零元素囊陡，就向右尋找最靠近它的非零元素芳绩，交換兩者位置
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
這個(gè)算法的復(fù)雜度很好分析，兩個(gè)"for-loop"的結(jié)構(gòu)撞反，顯然是O(n^2)的示括。在leetcode上提交后的結(jié)果如下：
可以看到全部的“testcase”都通過了，但執(zhí)行效率只打敗了約3%的“Python Submission”痢畜。顯然垛膝，這個(gè)算法的復(fù)雜度偏高了，還有更好的方法丁稀。
