你不可不會的幾種移動零的方法-有解無憂

前言

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

移動零

解題思路

根據題意，要把陣列中所有 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)」，未開辟額外的存盤空間，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288211.html

標籤：其他

上一篇：04-拉格朗日對偶問題和KKT條件

下一篇：什么是人工智能？你需要知道的關于人工智能的一切