这题源自Facebook和Bloomberg。
解法
class Solution {
public:
void moveZeroes(vector<int>& nums) {
vector<int> nonZeroElements;
for(int i=0;i<nums.size();i++)
if(nums[i])
nonZeroElements.push_back(nums[i]);
for(int i=0;i<nonZeroElements.size();i++)
nums[i]=nonZeroElements[i];
for(int i=nonZeroElements.size();i<nums.size();i++)
nums[i]=0;
}
};
时间复杂度O（n）空间复杂度O（n）。
class Solution {
public void moveZeroes(int[] nums) {
int a=nums.length;
int x=0;
int[] map=new int[nums.length];
for(int i=0;i<a;i++)
{
if(nums[i]!=0)
{
map[x]=nums[i];
x++;
}
}
for(int m=0;m<x;m++)
nums[m]=map[m];
for(int i=x;i<nums.length;i++)
nums[i]=0;
}
}
此问题还可以优化
优化策略在于以上解法使用了辅助空间，使得空间复杂度为O（n），现在可以在原数组上操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k=0;//nums中[0...k)的元素均为非零元素
//遍历到第i个元素后，保证[0...i]中所有非零元素
//都按照顺序排列在[0...k)中
for(int i=0;i<nums.size();i++)
if(nums[i])
nums[k++]=nums[i];
//将nums剩余的位置放置为0
for(int i=k;i<nums.size();i++)
nums[i]=0;
}
};
优化后时间复杂度为O(n)，空间复杂度为O(1)。
接下来的方法则是不改变，设游标k，遍历。如果有非零的则交换位置。k也变为相应的值。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k=0;//nums中[0...k)的元素均为非零元素
//遍历到第i个元素后，保证[0...i]中所有非零元素
//都按照顺序排列在[0...k)中
//同时，[k...i)为0
for(int i=0;i<nums.size();i++)
if(nums[i])
if(i!=k)
swap(nums[k++],nums[i]);
else//i==k
k++;//避免全是0
}
};
感想：考虑东西要全面
