leetcode 283 题解
很经典的双指针题目。
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= $10^4$
$-2^{31}$ <= nums[i] <= $2^{31} - 1$
思路
暴力解法
用vector的erase操作直接删除0，然后在结尾用push操作补0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
if(nums.size() == 1) return;
int count = 0, index = 0;
auto it = nums.begin();
while(it != nums.end()) {
int temp = *it;
if(temp==0) {
count++;
nums.erase(it);
continue;
}
else
++it;
}
for (int i = 0; i < count; i++)
nums.push_back(0);
return;
}
};
|
双指针
用一个变量 i 指示当前位置，一个变量 j 指示即将要被替换的位置，即双指针。当 nums[i] 为非0数时，将 nums[i] 替换到 nums[j] ，然后 j++ 。最后，从 j 开始到数组结束，全部替换成 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0, j = 0;
for (i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
nums[j] = nums[i];
j++;
}
}
for (i = j; i < nums.size(); i++) {
nums[i] = 0;
}
return;
}
};
|
