LeetCode 笔试题 Move Zeroes（将0移动到末尾）

问题描述 

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

代码1.

思路：把所有的0移到最后面 = 把所有不是0的数与此时数组最前面的0交换位置。

具体做法：两个指针，遍历整个数组：

第一个指针之前的数都不是0（一般情况它本身指的数是0）；

第一个指针和第二个指针中间的数都是0；

这个时候只要第二个指针指向的数不是0，就可以交换两个指针指向的值。

 

void moveZeroes(vector<int>& nums)
{
	for (int beforeItNotZero = 0, cur = 0; cur < nums.size(); cur++)
	{
		if (nums[cur] != 0) 
		{
			swap(nums[beforeItNotZero], nums[cur]);
			beforeItNotZero++;
		}
	}
}

 

代码2.

思路：把0删了，记录0的个数，再加在最后面。

//!!!!! 这里使用了迭代器进行erase，需要对迭代器进行更新防止迭代器失效
void moveZero(vector<int>&nums)
{
	auto it = nums.begin();
	int count = 0;
	while (it != nums.end())
	{
		if (*it != 0)
		{
			it++;
		}
		else
		{
			it = nums.erase(it);//注意迭代器需要更新
			count++;
		}
	}
	for (int i = 0; i < count; i++)
	{
		nums.push_back(0);
	}

}