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中使用就地算法将零转移到列表的末尾可以简化代码效率和实用性。