算法笔记_面试题_2.移动零(将数组的的0元素移到末尾)

问题

283. 移动零

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

示例:

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

说明:

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

分析

• 使用交换0和非0元素的方式，实现所有0都到末尾。
• 关键点在于确定什么时候交换。

最优解之一：

说明： 索引i用来遍历数组；索引j用来“始终”指向0元素的位置，j在交换过之后，直接+1，使其一直指向0的元素。特殊情况在于初始位置（i=0, j=0）时，如数组arr若是[7,0,3,0,9]时，第一次交换arr[i=0] 和arr[j=0],即自己跟自己交换了下，交换完后，j=j+1指向了0的元素位置。区别与去除有序数组中重复元素的算法：这里是：1）比较是否等0；2）不等0就先交换；3）再移动指针（索引j）。 去除有序数组中重复元素的算法是1）比较与前一个元素是否相等，2）不等先移动指针（索引j），3）再直接覆盖重复元素。

动画演示：

代码：

#include 
#include 
#include 

void moveZeroToEnd(std::vector& nums)
{
	int j = 0;
	int tmp = 0;
	for (int i = 0; i < nums.size(); ++i)
	{
		if (nums[i] != 0)
		{
			tmp = nums[i];
			nums[i] = nums[j];
			nums[j] = tmp;
			++j;
		}
	}
}

测试：

int main(int argc, char* argv[])
{
	std::vector ver = { 0,7,3,0,9 };
	moveZeroToEnd(ver);
	for (int i = 0; i < ver.size(); ++i)
	{
		std::cout