Code & Func

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

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

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