Java 程序将所有零移到数组开头

在 Java 中将所有零移到数组开头可以通过多种方法实现。在这里，我们将探讨三种不同的方法：使用辅助数组、原地交换和双指针技术。每种方法都将通过完整的 Java 代码进行解释和说明。

方法 1：使用辅助数组

此方法涉及创建一个额外的数组来分别存储零和非零元素。

文件名：MoveZerosToStart.java

输出

 
[0, 0, 0, 1, 2, 3, 4]   

解释

在辅助数组方法中，我们遍历数组三次。首先，我们计算零的数量并将它们放入新数组中。其次，我们将非零元素放入新数组中。

最后，我们将新数组复制回原始数组。尽管有这些多次遍历，但每次遍历都是线性的，因此总体时间复杂度为 O(n)，其中 n 是数组的长度。这种方法很简单，但需要与数组大小成比例的额外空间。

方法 2：原地交换

此方法通过原地将零交换到数组前面来最大程度地减少空间复杂度。

文件名：MoveZerosToStart.java

输出

 
[0, 0, 0, 1, 2, 3, 4]   

解释

在此方法中，我们遍历数组一次，在遇到零时将其交换到前面。这是通过维护一个用于放置零的索引，并在遇到零时将其与当前元素交换来实现的。

由于我们只遍历数组一次并执行常数时间交换，因此在最佳、最差和平均情况下，时间复杂度均为 O(n)。空间复杂度为 O(1)，因为我们只使用几个额外的索引变量。

方法 3：双指针技术

此方法使用两个指针有效地将零移到数组开头，而无需额外空间。

文件名：MoveZerosToStart.java

输出

 
[0, 0, 0, 1, 2, 3, 4]   

解释

在此方法中，我们使用两个从数组相反两端开始的指针。一个指针从左边移动以查找非零元素，另一个指针从右边移动以查找零。当在右边找到零，在左边找到非零元素时，它们将被交换。

这个过程会一直持续到指针相遇。每个元素最多被处理一次，因此在最佳、最差和平均情况下，时间复杂度均为 O(n)。由于只使用了几个额外的变量，因此空间复杂度为 O(1)。

结论

所有三种方法在最佳、最差和平均情况下都表现出 O(n) 的线性时间复杂度。然而，辅助数组方法使用了与数组大小成比例的额外空间，而原地交换和双指针技术则以 O(1) 的常数空间复杂度运行。因此，原地交换和双指针技术通常在空间效率方面更优。