LeetCode 283. 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的数字”永远不可能向后移动,其只会向前移动或者原地不动,所以我们使指针i
指向第一个值为0
的元素(初始值为0,即指向第一个元素,注意这里并不要求其指向的元素值一定是0
,只是说我们不能确定其一定不为0
),然后指针j
按顺序遍历数组,每当j
指向的元素值不为0
时,就给i
指向的元素赋值为j
指向元素的值,并且将i
指针向后移动一位;知道j
遍历完成后,这时就能确定i
及i
之后的元素值全都应该是0
,所以给其后元素全部赋值0
就好了。
拿示例[0, 1, 0, 3, 12]
演示一遍:
0, 1, 0, 3, 12
^^
ij
0, 1, 0, 3, 12
^ ^
i j
1, 1, 0, 3, 12
^ ^
i j
1, 1, 0, 3, 12
^ ^
i j
1, 3, 0, 3, 12
^ ^
i j
1, 3, 12, 3, 12
^ ^
i j
1, 3, 12, 0, 12
^ ^
i j
1, 3, 12, 0, 0
^ ^
i j
output: [1, 3, 12, 0, 0]
Python
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = 0
for num in nums:
if num != 0:
nums[i] = num
i += 1
while i < len(nums):
nums[i] = 0
i += 1
Java
public class Solution {
public void moveZeroes(int[] nums) {
int i = 0;
for (int num : nums) {
if (num != 0) {
nums[i] = num;
i++;
}
}
while (i < nums.length) {
nums[i] = 0;
i++;
}
}
}
C++
class Solution {
public:
void moveZeroes(vector<int> &nums) {
int i = 0;
for (auto num : nums) {
if (num != 0) {
nums[i] = num;
i++;
}
}
while (i < nums.size()) {
nums[i] = 0;
i++;
}
}
};