Move Zeroes(Easy)

题目描述

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.

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

Example

Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

题目链接

解题思路

从前往后遍历数组，设置两个指针，一个指针用来找到第一个 0， 另一个指针找到0的位置后面第一个非零数。交换即可。

时间复杂度：O(n)， n为数组长度

空间复杂度：in place...

参考代码

class Solution {
public:
    /**
     * @param nums an integer array
     * @return nothing, do this in-place
     */
    void moveZeroes(vector<int>& nums) {
        // Write your code here
        int i = 0, j, n = nums.size();
        while (i < n && nums[i]) ++ i;
        while (i < n) {
            j = i + 1;
            while (j < n && !nums[j]) ++ j;
            if (j < n) swap(nums[i], nums[j]);
            else break;
            ++ i;
        }
    }
};