力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0283. 移动零
题目地址(283. 移动零)
https://leetcode-cn.com/problems/move-zeroes/
题目描述
1
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
2
3
示例:
4
5
输入: [0,1,0,3,12]
6
输出: [1,3,12,0,0]
7
说明:
8
9
必须在原数组上操作,不能拷贝额外的数组。
10
尽量减少操作次数。
Copied!
前置知识
数组
双指针
公司
阿里
腾讯
百度
字节
bloomberg
facebook
思路
如果题目没有要求 modify in-place 的话,我们可以先遍历一遍将包含 0 的和不包含 0 的存到两个数组,然后拼接两个数组即可。 但是题目要求 modify in-place, 也就是不需要借助额外的存储空间,刚才的方法空间复杂度是 O(n).
那么如果 modify in-place ,空间复杂度降低为 1 呢?
其实可以使用
读写双指针
来做。具体来说使用一个慢指针表示写指针,快指针表示读指针。
具体来说:读指针不断往后移动。如果遇到非 0,则将读到的值写入写指针,触发写指针移动(其他情况写指针不动),读指针走到头算法结束。经过这样的处理,最终写指针的位置前面就是所有的非 0 数了, 最后将写指针后的 位置全部修改为 0 即可。
关键点解析
读写双指针
代码
语言支持:JS, C++, Java,Python
JavaScript Code:
1
/**
2
* @param {number[]} nums
3
* @return {void} Do not return anything, modify nums in-place instead.
4
*/
5
var
moveZeroes
=
function
(
nums
)
{
6
let
index
=
0
;
7
for
(
let
i
=
0
;
i
<
nums
.
length
;
i
++
)
{
8
const
num
=
nums
[
i
];
9
if
(
num
!==
0
)
{
10
nums
[
index
++
]
=
num
;
11
}
12
}
13
14
for
(
let
i
=
index
;
i
<
nums
.
length
;
i
++
)
{
15
nums
[
index
++
]
=
0
;
16
}
17
};
Copied!
C++ Code:
解题思想与上面 JavaScript 一致,做了少许代码优化(非性能优化,因为时间复杂度都是 O(n)): 增加一个游标来记录下一个待处理的元素的位置,这样只需要写一次循环即可。
1
class
Solution
{
2
public
:
3
void
moveZeroes
(
vector
<
int
>&
nums
)
{
4
vector
<
int
>
::
size_type nonZero
=
0
;
5
vector
<
int
>
::
size_type next
=
0
;
6
while
(
next
<
nums
.
size
())
{
7
if
(
nums
[
next
]
!=
0
)
{
8
// 使用 std::swap() 会带来 8ms 的性能损失
9
// swap(nums[next], nums[nonZero]);
10
auto
tmp
=
nums
[
next
];
11
nums
[
next
]
=
nums
[
nonZero
];
12
nums
[
nonZero
]
=
tmp
;
13
++
nonZero
;
14
}
15
++
next
;
16
}
17
}
18
};
Copied!
Java Code:
1
class
Solution
{
2
public
void
moveZeroes
(
int
[]
nums
)
{
3
// 双指针
4
int
i
=
0
;
5
for
(
int
j
=
0
;
j
<
nums
.
length
;
j
++
)
6
{
7
// 不为0,前移
8
if
(
nums
[
j
]
!=
0
)
9
{
10
int
temp
=
nums
[
i
];
11
nums
[
i
]
=
nums
[
j
];
12
nums
[
j
]
=
temp
;
13
i
++
;
14
}
15
}
16
}
17
}
Copied!
Python Code:
1
class
Solution
:
2
def
moveZeroes
(
self
,
nums
:
List
[
int
])
->
None
:
3
"""
4
Do not return anything, modify nums in-place instead.
5
"""
6
slow
=
fast
=
0
7
while
fast
<
len
(
nums
):
8
if
nums
[
fast
]
!=
0
:
9
nums
[
fast
],
nums
[
slow
]
=
nums
[
slow
],
nums
[
fast
]
10
slow
+=
1
11
fast
+=
1
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0263. 丑数
下一个
0342. 4 的幂
最近更新
1yr ago
复制链接
内容
题目地址(283. 移动零)
题目描述
前置知识
公司
思路
关键点解析
代码