JavaScript中將零移動到列表末尾的原地演算法

---

有效地操作資料結構是現代軟體開發的關鍵方面。在JavaScript中，一個常見的任務是將陣列中的所有零移動到末尾，同時保持非零元素的順序。雖然有多種方法可以實現這一點，但就地演算法是一種特別有效的技術，它避免了額外的記憶體開銷。在本討論中，我們將仔細研究JavaScript中將零移動到陣列末尾的就地演算法的複雜性，探討其背後的原理，並提供系統的執行步驟。透過掌握這項技術，軟體開發者可以改進他們的程式碼，並提高應用程式的整體效率。

問題陳述

待解決的問題是序列中存在零，這可能會不利地影響後續操作的計算效率。本研究的目標是設計一種能夠有效地重新排序序列的技術，即將零放在序列的末尾，而不改變其他非零元素的相對位置。預期的方法力求透過僅遍歷一次序列來執行零的重新定位，從而最佳化過程的時間複雜度。

為了舉例說明這個問題，考慮輸入列表

[2, 5, 0, 1, 0, 8, 0, 3]

其中0代表零。

期望的輸出將是

[2, 5, 1, 8, 3, 0, 0, 0]

其中零已移動到列表的末尾，同時保留了非零元件的初始順序。

方法

在本文中，我們將看到幾種不同的方法來解決上述JavaScript中的問題：

• 雙指標法

• 計數和填充法

方法一：雙指標法

為了將列表中的零與非零元素分開，在列表的開頭初始化兩個指標i和j。使用指標i遍歷列表。如果i處的元素非零，則將其與j處的元素交換，並將兩個指標都遞增。如果i處的元素為零，則只遞增i指標。繼續此過程，直到i到達列表的末尾。最後，所有非零元素都將位於左側，而零則自然地位於右側。

示例

moveZerosToEnd函式以陣列nums作為輸入，並原地將零移動到末尾。它使用兩個指標i和j，i遍歷陣列，j跟蹤非零元素的位置。while迴圈持續到i到達末尾。如果i處的元素非零，則使用陣列解構進行i和j之間的交換，並且j遞增。如果i處的元素為零，則不進行交換，並且只有i遞增。迴圈結束後，函式返回修改後的nums陣列，其中非零元素在左側，零在右側。

function moveZerosToEnd(nums) {
   let i = 0;
   let j = 0;
   const len = nums.length;
 
   while (i < len) {
      if (nums[i] !== 0) {
         [nums[i], nums[j]] = [nums[j], nums[i]];
         j++;
      }
      i++;
   }
 
   return nums;
}
 
// Example usage:
const nums = [0, 1, 0, 3, 12];
console.log(moveZerosToEnd(nums));

輸出

以下是控制檯輸出：

[ 1, 3, 12, 0, 0 ]

方法二：計數和填充法

為了轉換列表，首先，初始化一個計數變數來跟蹤零的數量。然後，遍歷列表，為找到的每個零遞增計數。建立一個新陣列來儲存轉換後的結果。再次遍歷列表，將非零元素追加到新陣列中。最後，將計數個零追加到新陣列中。返回新陣列作為轉換後的結果。

示例

moveZerosToEnd函式以陣列nums作為輸入，並原地將零移動到末尾。它初始化一個計數變數來跟蹤遇到的零的數量，並建立一個空的結果陣列。for迴圈遍歷nums陣列，為零遞增計數並將非零元素推送到結果陣列中。迴圈結束後，while迴圈執行計數次，將零推送到結果陣列中並遞減計數。該函式返回修改後的結果陣列，其中非零元素後跟零。

function moveZerosToEnd(nums) {
   let count = 0;
   const result = [];
 
   for (let i = 0; i < nums.length; i++) {
      if (nums[i] === 0) {
         count++;
      } else {
         result.push(nums[i]);
      }
   }
 
   while (count > 0) {
      result.push(0);
      count--;
   }
 
   return result;
}
 
// Example usage:
const nums = [0, 1, 0, 3, 12];
console.log(moveZerosToEnd(nums));

輸出

以下是控制檯輸出：

[ 1, 3, 12, 0, 0 ]

結論

總而言之，在JavaScript中使用就地演算法將零重新定位到列表末尾是一種明智且實用的解決方案，可以提高Web應用程式的效率。這種演算法策略在記憶體消耗至關重要的場合非常有利，因為它避免了建立新的列表，而是重新排列現有的列表。存在多種執行此方法的技術，包括使用多個指標、遞迴函式或兩者的結合。因此，開發人員必須根據他們特定的約束和需求選擇最合適的技術。最終，在JavaScript中使用就地演算法將零轉移到列表的末尾可以簡化程式碼效率和實用性。