1.移动零
题目描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例：
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
解题思路：
-
right指针一直往后移动，当nums[right]非0时和left指向的元素交换，然后left往后移动。
-
如果nums只有一个元素如[1]，那么直接交换没有影响，两外left变为1，没有访问数组是不会越界的。
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for(int left = 0,right = 0; right < nums.size();right++)
{
if(nums[right] != 0)
{
swap(nums[left],nums[right]);
left++;
}
}
}
};
2.复写零
题目描述：
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例：
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解题思路：
方法一：O(N^2)
- 使用index指针遍历，当index下标指向的元素是0将该位置往后的元素整体往后移动。腾出的那个位置填上0即可。
- 注意判断index刚好为最后一个且为0的特殊情况
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
for(int index = 0;index < arr.size();index++)
{
if(arr[index] == 0)
{
for(int tmp = arr.size() -1;tmp > index;tmp--)
{
arr[tmp] = arr[tmp-1];
}
if(index + 1 < arr.size())
{
arr[index+1] = 0;
index++;
}
}
}
}
};
方法二：（O(N)）
-
方法一，当找到index下标指向的元素为0，然后从前往后移动元素，浪费时间。能不能从后往前移动？[快慢双指针]
-
当left下标的元素非0时right++，为0则right+=2。最终right指向最后一个位置，right和left恰好腾出来两个位置，为两个0插入增加空间。（这起始位置很巧妙）
-
特殊情况，left指向的位置由于空间不足，无法添加一个0，而且right也越界了。arr[arr.size() -1] = 0，right -=2，left–。
-
从后往前移动，当arr[left]非0，移动即可，arr[left]为了添加一个0
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int left = 0,right = -1;
while(left < arr.size())
{
if(arr[left] != 0)right++;
else right +=2;
if(right >= arr.size() - 1)break;
left++;
}
if(right == arr.size())
{
arr[arr.size() -1] = 0;
left--;
right-=2;
}
while(left >= 0)
{
if(arr[left] != 0)
{
arr[right] = arr[left];
right--;
}
else
{
arr[right--] = 0;
arr[right--] = 0;
}
left--;
}
}
};
