双指针#简单#移动零

前文

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

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

输入: nums = [0]
输出: [0]

正文

class Solution {
public:
    void moveZeroes(vector<int>& nums) {

    }
};

• 形参为数组引用，且函数为空类型
• swap函数交换两个位置的元素

解法1

思路：

假设有下数组：

{1, 0, 10, 0, 2, 0, 0, 3}
i = 0;
j = nums.size()-1 = 7;

{1, 3, 10, 0, 2, 0, 0, 0}
i = 1;
j = nums.size()-1 = 7;

{1, 3, 10, 2, 0, 0, 0, 0}
i = 3;
j = nums.size()-4 = 4;

end if i >= j

分别从前开始和从结尾两个方向设置i，j位置变量相向遍历，开头遇到0则交换结尾遇到非0，结束条件是i<=j， 但需要满足题意，保持非0的相对顺序，因此变量i，j不能相向遍历，得从开头开始遍历：

{1, 0, 10, 0, 2, 0, 0, 3}
i = 0;
j = i+1;

{1, 0, 10, 0, 2, 0, 0, 3}
i = 1;
j = 2;

{1, 10, 0, 0, 2, 0, 0, 3}
i = 2;
j = 4;

{1, 10, 2, 0, 0, 0, 0, 3}
i = 3;
j = 7;

{1, 10, 2, 3, 0, 0, 0, 0}
end if j == nums.size()

代码：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
		int i = 0, j;
		for(i; i < nums.size(); ++i) {
			if (nums[i] == 0) {
				j = i + 1;
				for (j; j < nums.size(); ++j) {
					if (nums[j]){
						int tmp = nums[i];
						nums[i] = nums[j];
						nums[j] = tmp;
						break;
					}
				}
			}
		}
    }
};

声明两个i，j两个位置变量，i = 0开始，每次找到0的元素，即在此位置+1处开始寻找不为0元素， 找到交换，重复这一过程，每个过程每次直到j == nums.size() - 1;结束。

可以优化的点：

• 如果j变量过程一直向后没找到非0，可以结束

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
		int i = 0, j;
		for(i; i < nums.size(); ++i) {
			if (nums[i] == 0) {
				j = i + 1;
				bool flag = true;
				for (j; j < nums.size(); ++j) {
					if (nums[j]){
						flag = false;
						swap(nums[i], nums[j]);
						break;
					}
				}
				if (flag)
					return;
			}
		}
    }
};

定义一个变量，没找到则return。