C++程序将所有零移动到数组末尾

给定一个随机数的数组，在给定数组中将所有0的项推到数组的末尾。例如，如果给定的数组是{1，9，8，4，0，0，2，7，0，6，0}，则应更改为{1，9，8，4，2，7，6，0，0，0，0}。所有其他元素的顺序应保持不变。预计的时间复杂度为O(n)，额外空间为O(1)。

例如：

输入:  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
输出: arr[] = {1, 2, 4, 3, 5, 0, 0};

输入: arr[]  = {1, 2, 0, 0, 0, 3, 6};
输出: arr[] = {1, 2, 3, 6, 0, 0, 0};

可以有很多方法来解决这个问题。以下是解决此问题的一种简单有趣的方法。

从左到右遍历给定的数组‘arr’。在遍历时，维护数组中非零元素的计数。让计数为‘count’。对于每个非零元素arr[i]，将元素放在‘arr[count]’的位置，并增加‘count’。遍历完成后，所有非零元素已经被移至前面，并将‘count’设置为第一个0的索引。现在，我们所需要做的就是运行一个循环，将所有元素从‘count’到数组的末尾变为零。

以下是上述方法的实现。

// 一个将所有零移动到数组末尾的C++程序
#include <iostream>
using namespace std;
 
// 将所有零推到数组的末尾的函数
void pushZerosToEnd(int arr[], int n)
{
    int count = 0;  // 数组中非零元素的计数
 
    // 遍历数组。如果遇到的元素是非零，则将索引“count”的元素替换为此元素
    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i]; // 这里增加了计数
 
    // 现在，所有非零元素已经被移至前面，并将‘count’设置为第一个0的索引。
    // 让所有元素从count到末尾变为零。
    while (count < n)
        arr[count++] = 0;
}
 
// 测试上述函数的驱动程序
int main()
{
    int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    pushZerosToEnd(arr, n);
    cout << "压缩数组后的数组：\n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

输出:

压缩数组后的数组：
1 9 8 4 2 7 6 9 0 0 0 0

时间复杂度: ** O(n)，其中n是输入数组中元素的数量。

辅助空间: O(1)

其他方法：

假设开始元素为枢轴，当遍历数组时，如果遇到非零元素，则将该元素与枢轴交换，并增加索引。这将继续进行，直到所有非零元素放在左侧，所有零放在右侧。

#include <iostream>
using namespace std;
 
void swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
 
// 将数组中所有的 0 移动到数组的末尾
void fun(int A[], int n)
{
    int j = 0;
 
    // 当我们遇到一个非零元素时，将 `j` 递增， 然后将该元素放置在枢轴之前。
    for (int i = 0; i < n; i++) {
        if (A[i] != 0) // 枢轴为 0
        {
            swap(A, i, j);
            j++;
        }
    }
}
 
int main()
{
    int A[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5, 0 };
    int n = sizeof(A) / sizeof(A[0]);
 
    fun(A, n);
 
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
 
    return 0;
}