0283. 移动零
题目地址(283. 移动零)
https://leetcode-cn.com/problems/move-zeroes/
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]说明:必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。前置知识
双指针
公司
阿里
腾讯
百度
字节
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:
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */var moveZeroes = function (nums) { let index = 0; for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (num !== 0) { nums[index++] = num; } } for (let i = index; i < nums.length; i++) { nums[index++] = 0; }};C++ Code：
解题思想与上面 JavaScript 一致，做了少许代码优化（非性能优化，因为时间复杂度都是 O(n)）： 增加一个游标来记录下一个待处理的元素的位置，这样只需要写一次循环即可。
class Solution {public: void moveZeroes(vector<int>& nums) { vector<int>::size_type nonZero = 0; vector<int>::size_type next = 0; while (next < nums.size()) { if (nums[next] != 0) { // 使用 std::swap() 会带来 8ms 的性能损失 // swap(nums[next], nums[nonZero]); auto tmp = nums[next]; nums[next] = nums[nonZero]; nums[nonZero] = tmp; ++nonZero; } ++next; } }};Java Code:
class Solution { public void moveZeroes(int[] nums) { // 双指针 int i = 0; for(int j=0; j<nums.length; j++) { // 不为0，前移 if(nums[j] != 0) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; } } }}Python Code:
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ slow = fast = 0 while fast < len(nums): if nums[fast] != 0: nums[fast], nums[slow] = nums[slow], nums[fast] slow += 1 fast += 1复杂度分析
时间复杂度：$O(N)$
空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最后更新于
这有帮助吗？