Move-Zeroes

LeetCode

第44天。

今天的题目是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.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [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.

这道题目要求我们原地的移动元素，而且还要保持序列本身的顺序。

我们可以利用一下计数排序的思想，反正最后都是0,我只要算出有几个0要放在最后，我就可以很方便的产生后缀啦，所以这里先遍历一遍序列记录0的个数，然后我们发现其实每个元素向前移动多少格是和它前面有多少个0有关的,so ：

1
2
3
4
5
6
7
8
9
10
void moveZeroes(vector<int>& nums) {
    int zero = 0,size = nums.size(),i,j;
    for(i = 0;i < size;i++) {
        if (nums[i] == 0) zero++;
        else if (zero != 0) nums[i-zero] = nums[i];
    }
    j = size - 1;
    size -= zero;
    while(j >= size) nums[j--] = 0;
}

虽然写的不是很优雅的样子，但是这个思路是正确的，还有dicuss中的解法也是这个思路。

1
2
3
4
5
6
7
8
9
10
11
12
void moveZeroes(vector<int>& nums) {
    int j = 0;
    // move all the nonzero elements advance
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[j++] = nums[i];
        }
    }
    for (;j < nums.size(); j++) {
        nums[j] = 0;
    }
}