移动零

题面

给定一个数组 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

进阶： 你能尽量减少完成的操作次数吗？

分析

• C++ 提供了一个函数 std::unique，用来移除容器中相邻的重复元素（注意不是所有重复元素，只是相邻的），返回一个迭代器，指向去重后容器的末尾位置（后续的元素依然存在，但属于 “无效” 区域）

• 如果可以使用额外的空间，那么可以分配一个新的数组，使用两个指针，一个指针遍历原数组，另一个指针指向新数组，当遇到 0 元素时，原指针移动，新指针不动；遇到非零元素时，新指针和原指针一起移动

  #include <vector>
  using namespace std;
  
  class Solution {
  public:
      void moveZeroesWithExtraSpace(vector<int>& nums) {
          // 1. 创建和原数组同大小的新数组，初始值默认0（省去后续补0步骤）
          vector<int> new_nums(nums.size(), 0);
          // 2. j是新数组的填充指针，初始指向第一个位置
          int j = 0;
          // 3. 遍历原数组，将非零元素填充到新数组
          for (int i = 0; i < nums.size(); ++i) {
              if (nums[i] != 0) {
                  new_nums[j] = nums[i];
                  j++; // 非零元素才移动填充指针
              }
              // 遇到0时，i移动、j不动，新数组对应位置保持初始的0
          }
          // 4. 将新数组拷贝回原数组
          nums = new_nums;
      }
  };

• 那么如何不使用额外的空间？可以从后往前遍历，遇到 0 时，就把 0 之后的元素向前覆盖，这样所需的操作次数很多

  #include <vector>
  using namespace std;
  
  class Solution {
  public:
      void moveZeroesInPlaceSlow(vector<int>& nums) {
          int n = nums.size();
          // 从后往前遍历数组（最后一个元素无需处理）
          for (int i = n - 2; i >= 0; --i) {
              if (nums[i] == 0) {
                  // 遇到0，将0后面的元素依次向前覆盖一位
                  int j = i;
                  while (j < n - 1) {
                      nums[j] = nums[j + 1];
                      j++;
                  }
                  // 最后一个位置设为0
                  nums[n - 1] = 0;
              }
          }
      }
  };

• 可以使用两个指针从前往后移动，一个指针指向更新后的新数组，另一个指针遍历旧的数组

• 当旧指针发现零元素时，旧指针移动，直到遇到非零元素，将非零元素存入新指针位置，新指针也移动

• 代码实现

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

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