283. Move Zeroes

  • 48.7%

https://leetcode.com/problems/move-zeroes/#/description

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:

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

方法一:

我的代码实现:

Oct 17, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int j=0;
for(int i=0; i<n; i++)
if(nums[i]!=0)
nums[j++] = nums[i];
for(;j<n; j++)
nums[j] = 0;
return;
}
};

https://discuss.leetcode.com/topic/32632/my-simple-c-solution

My simple C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
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;
}
}
};

方法二:

类似于快排partition的用法

我的代码实现:

Oct 21, 2017

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int pos = -1;
for(int i=0; i<nums.size(); i++)
if(nums[i]!=0)
swap(nums[++pos], nums[i]);
return;
}
};

https://discuss.leetcode.com/topic/24745/c-accepted-code

C++ Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
void moveZeroes(vector<int>& nums) {
int last = 0, cur = 0;

while(cur < nums.size()) {
if(nums[cur] != 0) {
swap(nums[last], nums[cur]);
last++;
}

cur++;
}
}

https://discuss.leetcode.com/topic/25077/one-line-c-code-20ms

One line c++ code, 20ms

The idea comes from the c++ erase/remove idiom.

1
2
3
4
5
6
class Solution {
public:
void moveZeroes(vector<int>& nums) {
fill(remove(nums.begin(), nums.end(),0), nums.end(), 0);
}
};

https://discuss.leetcode.com/topic/25163/c-1-line-or-3-lines-clean-code

C++ 1 line (or 3 lines) clean code

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

void moveZeroes(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); i++) {
if (nums[i] != 0) swap(nums[i], nums[j++]);
}
}

https://discuss.leetcode.com/topic/28941/very-simple-python-solutions

Very simple python solutions

Solution 1: traverse and swap last 0 and last non 0

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
last0 = 0
for i in range(0,len(nums)):
if (nums[i]!=0):
nums[i],nums[last0] = nums[last0],nums[i]
last0+=1

Solution 2 : one-liner from @toontong: use sort() with customized compare function

1
2
3
4
5
6
7
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort(cmp=lambda a,b: 0 if b else -1)
谢谢你,可爱的朋友。