283.Move Zeroes

Tags: Array Two Pointers

Links: https://leetcode.com/problems/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:

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

---

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int start = -1, end = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                start = i; break;
            }
        }

        if (start == -1) return;

        end = start + 1;
        while (end < n) {
            for (int i = end; i < n; ++i) {
                if (nums[i] != 0) {
                    end = i; break;
                }
            }

            std::swap(nums[start], nums[end]);
            ++start; ++end;
        }

    }
};

上面思路正确，但是代码过长，其实可以精简写法，容易联想起26题，去除重复元素。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int start = 0, end = 0;
        while (end < n) {
            if (nums[end]) {
                std::swap(nums[start++], nums[end]);
            }
            ++end;
        }
    }
};