283. 移动零

283. 移动零 - 力扣（LeetCode）

class Solution {
public:
  void moveZeroes(vector<int>& nums) {
    int Z{}, NZ;
    // Initialize Z.
    while (nums[Z] != 0) {
      ++Z;
      if (Z == nums.size())
        return;
    }

    NZ = Z;
    while (true) {
      while (nums[NZ] == 0) {
        ++NZ;
        if (NZ == nums.size())
          return;
      }
      std::swap(nums[Z], nums[NZ]);
      ++Z;
    }
  }
};

我这个解法好诡异啊真的，虽然非常符合我画出来的图，但总体上就是复杂很多。官方题解给出的解法就非常简洁：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

区别就在于我的思路是「零」和「非零」指针，而官方的解法则是划分「待处理」和「已处理」序列——利用「已处理」序列中无零的特性，从「待处理」序列中找零。

有一点很有意思：官方的题解当中无副作用的 swap() 执行的次数是比较多的，而我的题解当中每个 swap() 都是有用的。

二刷

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

虽然还是有点诡异，但是非常直观，而且也还算比较容易记。当然第二次写我又没想到官解的思路，行吧。

总体来说就是这道题的思路重点在于「维护非零元素的边界」。你可以看到我上面解法当中的 \(i\) 总是指向非零元素的尾后元素，并且针对 \([1,0]\) 这种测试用例，我是让 \(i\) 先走到第一个零元素，\(j\) 再找非零元素的。

官解的方法重点在于那个 if 分支——你可以发现 if 分支（注意，它没有 else）使得在处理数组的过程当中，永远存在 \(\text{left} \le \text{right}\) 的偏序关系，而分支条件使得 \(\text{right}\) 成为已被处理过的全部元素的尾后元素，\(\text{left}\) 则是已被处理过的非零元素的尾后元素。

三刷

class Solution {
public:
  void moveZeroes(vector<int>& nums) {
    int Last = 0, Cur = 0;
    while (true) {
      while (Cur != nums.size() && nums[Cur] == 0)
        ++Cur;
      if (Cur == nums.size())
        break;
      // Cur is not zero
      swap(nums[Last], nums[Cur]);
      ++Last;
      ++Cur;
    }
  }
};

我怎么感觉我这次写得比前两次都更简洁一点。虽然依旧是「标记最后一个非零元素」的思路。