你不可不會的幾種移動零的方法

2021 年 6 月 20 日
筆記

前言

本文主要介紹通過「末尾補零」以及「交換零元素與非零元素」的策略來解答此題，供大家參考，希望對大家有所幫助。

移動零

解題思路

根據題意，要把數組中所有 0 移動到數組的末尾，還要保持非零元素的「相對位置」，只需要遍歷一遍數組，找出「非零元素」，然後將找出的非零元素替換原數組的元素，原數組中「未替換的元素全部用零去替換」即可。

末尾補零法

「舉例」

以數組 nums =[0,1,0,3,12]為例子，如下圖示。

遍歷整個數組，找出所有非零元素。

替換

遍歷、查找和替換的完整過程，如下動圖示。

「說明」

不需要全部查找完數組中的非零元素之和，再去替換，可以「邊查找邊替換」，這樣就不需要「開闢額外空間存儲查找到的非零元素」。

Show me the Code

「C」

 1 void moveZeroes(int* nums, int numsSize){
 2     int j = 0;   //  區間[0...j)中存放非零元素
 3     for (int i = 0; i < numsSize; ++i) {
 4         /* 尋找數組中所有的非零元素，並保存在區間[0...j)中 */
 5         if (nums[i] != 0) {
 6             nums[j++] = nums[i]; 
 7         }
 8     }
 9 
10     /* 原數組未被非零元素替換的元素全部置為0 */
11     while (j < numsSize) {
12         nums[j++] = 0;
13     }
14 }

View Code

「C++」

 1 void moveZeroes(vector<int>& nums) {
 2     int j = 0;
 3     for (int i = 0; i < nums.size(); i++) {
 4         if (nums[i] != 0) {
 5             nums[j++] = nums[i];
 6         }
 7     }
 8     
 9     while (j < nums.size()) {
10         nums[j++] = 0;
11     }
12 }

View Code

「Python3」

1 def moveZeroes(self, nums):
2     j, length = 0, len(nums)
3     for i in range(length):
4         if nums[i] != 0:
5             nums[j] = nums[i]
6             j += 1
7     while j < length:
8         nums[j] = 0
9         j += 1

View Code

「Golang」

 1 func moveZeroes(nums []int)  {
 2     j, length := 0, len(nums)
 3     for i := 0; i < length; i++ {
 4         if nums[i] != 0 {
 5             nums[j] = nums[i]
 6             j++
 7         }
 8     }
 9     
10     for j < length {
11         nums[j] = 0
12         j++
13     }
14 }

View Code

「複雜度分析」

時間複雜度：「O(n)」，其中 n 是數組的長度，需要遍歷一遍數組。

空間複雜度：「O(1)」，未開闢額外的存儲空間。

交換法

由於題目的說明中要求「盡量減少操作次數」，因此可以考慮通過「遍歷查找到非零元素，再交換非零元素與當前數組的第一個零元素」的策略，來減少方法一種的補零操作，從而減少操作次數。

「舉例」

還是以數組 nums =[0,1,0,3,12]為例子，其交換過程如下圖示。

由於 nums[1] 為非零元素，nums[0] 為零元素，因此交換它們。

其完整查找和交換過程，如下動圖示。

Show me the Code

「C++」

 1 void moveZeroes(vector<int>& nums) {
 2     for (int i = 0, k = 0; i < nums.size(); i++) {
 3         if (nums[i] != 0) {
 4             if (i != k) {
 5                 swap(nums[k++], nums[i]);
 6             } else {
 7                 k++;
 8             }     
 9         }
10     }
11 }

View Code

「Python3」

1 def moveZeroes(self, nums: List[int]) -> None:
2     k, length = 0, len(nums)
3     for i in range(length):
4         if nums[i] != 0:
5             if i != k:
6                 nums[k], nums[i] = nums[i], nums[k]
7                 k += 1
8             else:
9                 k += 1

View Code

「Golang」

 1 func moveZeroes(nums []int)  {
 2     k, length := 0, len(nums)
 3     for i := 0; i < length; i++ {
 4         if nums[i] != 0 {
 5             if i != k {
 6                 nums[k], nums[i] = nums[i], nums[k]
 7                 k++
 8             } else {
 9                 k++
10             }
11         } 
12     }
13 }

View Code

「說明」

上述的代碼中都加了「i 是否等於 k」的判斷，這是因為如果數組中的元素都是「非零元素」，就不需要「自己與自己交換」，也算是一個小的優化。

「複雜度分析」

時間複雜度：「O(n)」，其中 n 是數組的長度，需要遍歷一遍數組。

空間複雜度：「O(1)」，未開闢額外的存儲空間。