塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-283 移动零

不能使用辅助数组,尽可能少的移动数组。

最初想法:

1
先去掉0,再补充0。感觉移动数组次数很多

官方

方法一:两次遍历(感觉也得移动很多次)

第一次遍历,记录非0的个数,并将非0值往前挪;
第二次遍历,补0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if not nums:
return nums
n = len(nums)
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[j] = nums[i]
j += 1
# 非0元素统计完了,剩下的都是0了
# 所以第二次遍历把末尾的元素都赋为0即可
for i in range(j,len(nums)):
nums[i] = 0

方法二: 一次遍历,两个游标

RE:https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/

1
2
j指向最后一个非零元素的下一个位置(换句话说,第一个0元素的位置);
i从头遍历,遇到非零元素,交换nums[i]与nums[j],将非零元素挪到左边,零挪到右边
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if not nums:
return nums
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i],nums[j] = nums[j],nums[i]
j += 1 #只有是非零元素,j才往前走
if help:小手一抖点个广告 or 大手一挥资助一下