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