Code & Func
2017-11-09

第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
}
上一条动态