283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Solution:

因为需要原地排序, 选择用交换.
让交换的次数尽可能的少, 从尾部向前找, 找到的第一个数交换到尾部, 然后让尾部”缩短”.

// 从右向左找到0, 用j标记位置, i交换到尾部, 找到下一个0, 交换到尾部之前的位置.
// Time:O(n^2), Space:O(1)
class Solution {
 public:
  void moveZeroes(vector<int>& nums) {
    
    int n = nums.size();
    int i = n-1, j;
    while (i >= 0) {
      if (nums[i] == 0) {
        while (i < n-1) {
          swap(nums[i], nums[i+1]); i++;
        }
        n--;
        i = j;
      }
      i--;
    }
  }
};

但应该还能考虑一种, 直接将0交换到尾部对应的位置, 而不是一步步交换;

这种交换的难点在于对, 要保持除0外的元素的顺序不变.