LeetCode 283. 移动零

思路

方法：双指针

令i = 0，循环遍历数组，直到i指向第一个值为0的元素
令j = i + 1, 循环遍历数组，直到j指向第一个值非0的元素
swap(nums[i],nums[j])
重复上述流程，直到i或j大于题中给出的数组长度

 1 class Solution {
 2 public:
 3     void moveZeroes(vector<int>& nums) {
 4         int i = 0, j;
 5         while(i < nums.size() && j < nums.size()) {
 6             //找到第一个值为0的下标i
 7             while(nums[i] != 0) {
 8                 ++i;
 9                 if(i >= nums.size()) {
10                     return;
11                 }
12             }
13 
14             j = i + 1;  //从i后面开始找
15             if(j >= nums.size()) {
16                 return;
17             }
18 
19             //找到第一个值不为0的下标j
20             while(nums[j] == 0) {
21                 ++j;
22                 if(j >= nums.size()) {
23                     return;
24                 }
25             }
26 
27             swap(nums[i], nums[j]);
28         }
29 
30     }
31 };

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)