Code & Fun

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

本文首发于Code & Fun