# 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啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。