Programa C++ para eliminar todas las apariciones de un elemento en una array

Aquí veremos cómo eliminar todas las ocurrencias de un elemento en una array usando un programa C++. A continuación se muestran los ejemplos:

Entrada: {1, 4, 3, 6, 8, 3, 9, 10, 3, 3, 7}
               objetivo=3
Salida: {1, 4, 6, 8, 9, 10, 7}

Entrada: {12, 11, 10, 17, 12, 4, 7, 12} 
            objetivo=12
Salida: {11, 10, 17, 4, 7}

Hay 2 formas de eliminar todas las ocurrencias de un elemento en una array en C++:

1. Enfoque de fuerza bruta.
2. Enfoque optimizado (cambio en el lugar).

Comencemos discutiendo cada uno de estos métodos en detalle.

1. Enfoque de fuerza bruta

En este método, cree otra array y copie todos los elementos excepto el elemento de destino. A continuación se muestra el programa C++ para eliminar todas las ocurrencias de un elemento en una array utilizando un enfoque de fuerza bruta:

// C++ program to remove all the
// occurrences
#include <iostream>
using namespace std;
 
void remove_all_occurrence(int arr[],
                          int target,
                          int n)
{
  int cnt = 0;
   
  // Counting all occurrence of
  // target element
  for(int i = 0; i < n; i++)
  {
    if(arr[i] == target)
      cnt++;
  }
       
  // Creating new array of
  // size = original size -
  // no. of target element
  int new_arr[n - cnt];
  int ind = 0;
  for(int i = 0; i < n; i++)
  {
    if(arr[i] != target)
    {
      new_arr[ind] = arr[i];
      ind++;
    }
  }
       
  // Printing the new array
  int m = (sizeof(new_arr) /
           sizeof(new_arr[0]));
  for(int i = 0; i < m; i++)
  {
    cout << new_arr[i] << " ";
  }
  return;
}
 
// Driver code
int main()
{
  int arr[]={1, 4, 3, 6, 8,
             3, 9, 10, 3, 3, 7};
  int target = 3;
  int n = (sizeof(arr) /
           sizeof(arr[0]));
  remove_all_occurrence(arr, target, n);
  return 0;
}

1 4 6 8 9 10 7 

Complejidad de tiempo: O(n)

Complejidad espacial: O(n)

2. Enfoque optimizado (cambio en el lugar)

En este método, desplace el elemento no objetivo hacia el lado izquierdo. 

1. Compruebe si el elemento actual es el elemento de destino o no.
2. Si es el elemento de destino, aumente la variable cnt .
3. Después de este elemento, todos los elementos no objetivo se desplazarán a la izquierda con el espacio de (n-cnt) .

A continuación se muestra el programa C++ para eliminar todas las apariciones de un elemento de una array utilizando un enfoque optimizado:

// C++ program to remove all occurrences
// of an element from an array using
// optimized approach
#include <iostream>
using namespace std;
 
void remove_all_occurrence(int arr[],
                          int target,
                          int n)
{
  int cnt = 0;
   
  // Shifting non target elements
  // to the left side
  for(int i = 0; i < n; i++)
  {
    if(arr[i] != target)
    {
      arr[i - cnt] = arr[i];
    }
    else
    {
      cnt++;
    }
  }
   
  // Printing the array
  for(int i = 0; i < (n - cnt); i++)
  {
    cout << arr[i] << " ";
  }
  return; 
}
 
// Driver code
int main()
{
  int arr[] = {1, 4, 3, 6, 8, 3,
               9, 10, 3, 3, 7};
  int target = 3;
  int n = (sizeof(arr) /
           sizeof(arr[0]));
  remove_all_occurrence(arr, target, n);
  return 0;
}

1 4 6 8 9 10 7 

• Complejidad de tiempo: O(n)
• Complejidad espacial: O(1)