LeetCode-283. 移动零【数组，双指针】

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

进阶：你能尽量减少完成的操作次数吗？
https://leetcode.cn/problems/move-zeroes/

解题思路一：首先想到的是双指针，但是不行，非零元素的位置会改变。

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

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

解题思路二：改进的是每次从当前0元素的位置取后面第一个非0元素替换过来。替换之和那个break非常重要!

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;++i)
            if(nums[i]==0){
                int temp=0;
                for(int j=i;j<n;++j)
                    if(nums[j]!=0){
                        temp=nums[j];
                        nums[j]=nums[i];
                        nums[i]=temp;
                        break;//只替换一次
                    }          
            }
    }
};

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

解题思路三：优化双指针，无论左指针是否为0元素，遇到非零元素直接交换即可。

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++;
        }
    }
};

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