题目描述:
给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
算法分析:
由于只能在原数组上操作，不能拷贝额外的数组，所以可以用双指针算法，两个指针相邻，当第一个指针指向为0时，交换两个指针指向的值，同时两个指针++，但是这样就只能将一个0移到末尾，所以在外面再加一重for循环。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=0;i<nums.size();++i)
for(int j=i,k=j+1;k<nums.size();j++,k++)
if(nums[j]==0) swap(nums[j],nums[k]);
}
};
但是这个提交后显示WA，通过了20 / 21 个通过测试用例。显示[0,0,1]输出错误，正确答案[1,0,0],我的答案[0,1,0].
通过分析，上述代码有一种情况不满足:当j,k遍历完一次,i的值还为0时,i++,那么这个0就被留在了原地.
怎么解决呢？
可以加一个if判断，当nums[i]==0时,i不变,j、k继续跑一遍，这样之前i指向的0就到队尾去了.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=0;i<nums.size();++i){
for(int j=i,k=j+1;k<nums.size();j++,k++)
if(nums[j]==0) swap(nums[j],nums[k]);
if(nums[i]==0) i--;
` }
}
};//但是这样调试显示TLE,那就换一下思路:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=0;i<nums.size();++i)
for(int j=i,k=j+1;k<nums.size();j++,k++){
if(nums[j]==0) swap(nums[j],nums[k]);
//if(nums[i]==0) i--;
if(nums[i]==0) swap(nums[i],nums[i+1]);
}
}
};//AC!
执行用时：756 ms, 在所有 C++ 提交中击败了5.57%的用户;内存消耗：9.3 MB, 在所有 C++ 提交中击败了5.06%的用户
这样的话:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=0;i<nums.size()-1;++i){
for(int j=i;j<nums.size()-1;j++)
if(nums[j]==0) swap(nums[j],nums[j+1]);
if(nums[i]==0) swap(nums[i],nums[i+1]);
}
}
};
执行用时：548 ms, 在所有 C++ 提交中击败了5.57%的用户;内存消耗：9 MB, 在所有 C++ 提交中击败了14.58%的用户
注意:这么简单的题肯定是用不到双重for循环的.
大佬思路:
双指针思路大致如下：一个慢（index）指针，一个快（i）指针；当快指针指向的值不等于0时，将其与慢指针（此时的慢指针指向待交换的位置）进行交换，并使慢指针往后挪一位，指向新的代交换位置。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int index=0;
for(int i=0;i<nums.size();++i)
if(nums[i]) nums[index++]=nums[i];
while(index<nums.size())
nums[index++]=0;
}
};
//整体思路设置一个index，表示非0数的个数，循环遍历数组;
//如果不是0，将非0值移动到第index位置,然后index + 1
//遍历结束之后，index值表示为非0的个数，再次遍历，index位置后的位置此时都应该为0.
//即先把非0的数往前放,后边再用0填充.可以看成双指针算法.
//执行用时：12 ms, 在所有 C++ 提交中击败了51.65%的用户;内存消耗：9.2 MB, 在所有 C++ 提交中击败了5.06%的用户
//此思路在C语言中时间超过98.73%.
继续对上面代码优化:
//可以直接交换nums[index]和nums[i]，就不用在循环一次了.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=0,index=0;i<nums.size();++i)
if(nums[i])
swap(nums[index++],nums[i]);
}
};
//执行用时：8 ms, 在所有 C++ 提交中击败了91.80%的用户;内存消耗：9.2 MB, 在所有 C++ 提交中击败了5.06%的用户
//整体思路从最终的位置来看,每个数要往前移动x位,而x等于这个数前0的个数,所以统计下每个数前有多少个0就行了.最后把末尾的0补上,这样每个数就只移动了一次,没有交换,直接覆盖就行.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int zerocount=0;
for(int i=0;i<nums.size();++i)
if(nums[i]==0) zerocount++;
else nums[i-zerocount]=nums[i];
while(zerocount)
nums[nums.size()-(zerocount--)]=0;
}
};
//执行用时：12 ms, 在所有 C++ 提交中击败了51.53%的用户;内存消耗：9.1 MB, 在所有 C++ 提交中击败了8.81%的用户
3.
