283.移动零
#leetcode#双指针 2025-01-26

Problem: 283. 移动零

思路

双指针大法

解题过程

fast开始移动，当fast第一次遇到0前slow和fast一致
当fast遇到0后就会快于slow，这样就会发生有效交换

复杂度

  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(1)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
//! 双指针 n,1
class Solution {
public:
  void moveZeroes(vector<int> &nums) {
    int slow = 0; // slow point to non-zero,fast the other
    for (int fast = 0; fast < nums.size(); ++fast) {
      if (nums[fast] != 0) {
        swap(nums[slow], nums[fast]);
        ++slow;
      }
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//!从后往前找0元素，找到就一步一步往后移 n^2,1
class Solution {
public:
  void moveZeroes(vector<int> &nums) {
    int zeroTag, NonZeroTag;
    for (int i = nums.size() - 1; i >= 0; --i) {
      if (nums[i] == 0) {
        int j = i;
        while (j + 1 < nums.size() && nums[j + 1] != 0) {
          swap(nums[j], nums[j + 1]);
          ++j;
        }
      }
    }
  }
};