Programa C++ para mover todos los ceros al final de la array – Part 1

Dada una array de números aleatorios, Empuje todos los ceros de una array dada al final de la array. Por ejemplo, si las arrays dadas son {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, debe cambiarse a {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. El orden de todos los demás elementos debe ser el mismo. La complejidad de tiempo esperada es O(n) y el espacio adicional es O(1).
Ejemplo: 
 

Input :  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
Output : arr[] = {1, 2, 4, 3, 5, 0, 0};

Input : arr[]  = {1, 2, 0, 0, 0, 3, 6};
Output : arr[] = {1, 2, 3, 6, 0, 0, 0};

Puede haber muchas maneras de resolver este problema. A continuación se muestra una forma sencilla e interesante de resolver este problema. 
Recorre la array dada ‘arr’ de izquierda a derecha. Durante el recorrido, mantenga el conteo de elementos distintos de cero en la array. Que el conteo sea ‘contar’. Para cada elemento distinto de cero arr[i], coloque el elemento en ‘arr[count]’ e incremente ‘count’. Después de completar el recorrido, todos los elementos distintos de cero ya se han desplazado al frente y ‘contar’ se establece como índice del primer 0. Ahora todo lo que tenemos que hacer es ejecutar un ciclo que hace que todos los elementos sean cero desde ‘contar’ hasta el final de la array
A continuación se muestra la implementación del enfoque anterior. 
 

// A C++ program to move all zeroes at the end of array
#include <iostream>
using namespace std;
 
// Function which pushes all zeros to end of an array.
void pushZerosToEnd(int arr[], int n)
{
    int count = 0;  // Count of non-zero elements
 
    // Traverse the array. If element encountered is non-
    // zero, then replace the element at index 'count'
    // with this element
    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i]; // here count is
                                   // incremented
 
    // Now all non-zero elements have been shifted to
    // front and  'count' is set as index of first 0.
    // Make all elements 0 from count to end.
    while (count < n)
        arr[count++] = 0;
}
 
// Driver program to test above function
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 << "Array after pushing all zeros to end of array :
";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Producción: 
 

Array after pushing all zeros to end of array :
1 9 8 4 2 7 6 9 0 0 0 0

Complejidad de tiempo: O (n) donde n es el número de elementos en la array de entrada.
Espacio Auxiliar: O(1)

OTRO ENFOQUE:

Asumiendo que el elemento de inicio es el pivote y mientras itera a través de la array si se encuentra un elemento distinto de cero, intercambie el elemento con el pivote e incremente el índice. Esto continúa hasta que todos los elementos distintos de cero se colocan hacia la izquierda y todos los ceros hacia la derecha.

#include <iostream>
using namespace std;
 
void swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
 
// Function to move all zeros present in an array to the end
void fun(int A[], int n)
{
    int j = 0;
 
    // when we encounter a non-zero, `j` is incremented, and
    // the element is placed before the pivot
    for (int i = 0; i < n; i++) {
        if (A[i] != 0) // pivot is 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;
}

1 2 3 4 5 0 0 0 0 0 

Complejidad de tiempo : O (n) donde n es el número de elementos en la array de entrada.
Espacio Auxiliar : O(1)

Consulte el artículo completo sobre Mover todos los ceros al final de la array para obtener más detalles.