題目描述

題目分析

在寫簡單題放松，看到這道題第一個想法是用STL庫函數，雖然知道大概要用雙指針之類的，但是庫函數爽哇。

class Solution {
public:void moveZeroes(vector<int>& nums) {stable_sort(nums.begin(), nums.end(), [](const auto &a, const auto &b) -> bool {if (a == 0) {return false;}if (b == 0) {return true;}return false;});}
};

雖然慢，但是我覺得這樣寫出來還是挺開心的。基本沒動腦子。我也不知道stable_sort函數是怎么實現的（可能需要以后看STL源碼了），但是我知道只需要定義小于運算，等于運算是通過a小于b為假并且b小于a實現的，通過自定義小于運算符，如果代碼緊湊一點，我覺得三行是可以解決的。

但是顯然上面的解法是O(nlogn)的
雙指針應該是可以覺得這種問題的，于是我寫了個另一個無腦代碼：

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();int i = 0;for (int j = 0; j < n; ++j) {if (nums[j]) {nums[i++] = nums[j];}}for (; i < n; ++i) nums[i] = 0;}
};

上面代碼應該是O(n)的，但是我看題解發現人家用的是交換，這樣的思想我覺得比較巧妙了，通過交換將0不斷往后積累。如果是０多１少，這樣的做法更好。但是我的代碼如果是１多０少我的復雜度更低。