LintCode539:MovingZeros

这题有两种解法&＃xff1a;用quicksort的partition或双指针。
Partition法:可以减少swap的次数&＃xff0c;但不能维持数组元素的相邻顺序。 正是因为partition的这个原因&＃xff0c;所以quicksort不是稳定排序。

代码下次补充。

双指针法: swap的次数较多&＃xff0c;可以维持数组元素的相邻顺序。

void moveZeroes(vector &nums) {int p1&＃61;0, p2&＃61;0;while(p2

注意&＃xff1a;
1&＃xff09;对于双指针法&＃xff0c;我的理解是&＃xff0c;0越多&＃xff0c;交换次数越少。
所以&＃xff0c;对于0很少的情况&＃xff0c;可以先预处理把非零元素复制到前部&＃xff0c;然后把后面的元素清零。代码如下(参考了九章的讨论)&＃xff1a;

public void moveZeroes(int[] nums) {int i &＃61; 0;for (int j &＃61; 0; j }


对于0很多的情况&＃xff0c;就可以直接用上面的双指针法了&＃xff0c;因为只需要一个循环。