Duda - Como eliminar numeros repetidos de un arreglo en C?

[palacio29]

Hola

Como veran soy bastante novato en C ,y desde la facultad me piden este tipo de ejercicio pero no logro hacerlo funcionar. He logrado realizar la carga de un arreglo sin incluir repetidos pero cuando estamos ingresando los datos...Pero una vez que tengo el arreglo cargado nose como modificar el arreglo para que me de sin repetidos.

Agradeceria cualquier ayuda

[csergioc]

Este ejemplo estaba en el foro, lo probé y funciona perfectamente, espero que te ayude!

Código [Seleccionar] Expandir


#include <stdio.h>

int main (void) {
        int v_original [10];
        int v_aux [10];
        int v_final [10];
        int cont,num,i,j=0,k,z=0 ;

        for (i=0; i<10; i++) {
                printf("Introduce el valor del array incial %d: ", i+1);
                scanf("%d",&v_original[i]);
        }


        for (i=0;i<10;i++) {
                cont=0;
                num=v_original[i];
                v_aux[j]=num;
                j++;
                for (k=0;k<10;k++)
                        if ( v_aux[k] == num )
                                cont++;

                if ( cont == 1 ) {
                        v_final[z]=num;
                        z++;
                }
        }


        printf("El array simplificado es: \n");
        for (i=0;i<z;i++)
                printf ("%d \n",v_final[i]);

        return 0;
}


[dwarf271]

Estoy con la misma problematica del muchacho, pero no entiendo ese codigo y lo probé y no funciona.

Saludos.

[Serapis]

Hay varia smaneras, una smás optimas que otras, y según el caso  hay un algoritmo (counting  Sort) que resulta el más efectivo pero puede incurrir en un costo excesivo de memoria (asocaidos al valor máximo y mínimo) y al mismo tiempo de tiempo (si el array es pequeño pero dichos valores son muy distantes entre sí...

Así que te indicaré la manera adecuada para todos los casos (y no solo números o número enteros).

1 - Ordenar el array.
2 - Recorrer el array con dos bucles.
El externo (el primero) empieza por el primer ítem en el array y acaba en el penúltimo. Este penúltimo, se irá reduciendo a medida que se tapen los repes con los que están por encima. Puede hacerse con un bucle while, condicionado a alcanzar el último -1, teniendo en cuenta que el último se va reduciendo en la medida en que aparezcan los repes.
El interno es también un bucle de tipo 'while' se repite el valor tomado en el primer bucle, la cuenta en este empieza (la primera vez solo) uno más arriba que el primero y acaba condicionado mientras se repita y no se alcanza el último índice del array.

Código [Seleccionar] Expandir


// Realiza 3 operaciones: 1-ordenar el array, bajar los no repes tapando los repes, y copia a un nuevo array los no repes.
Funcion EliminarRepes(array de enteros valores() )
   entero numRepes
   // 1º Ordenar el array
   Llamada a  Ordenar (valores) // da igual si se ordena de menor a mayor o de mayor a menor
   // 2º Bajar los no repes tapando los repes,
   numRepes = EliminarRepes2(valores)
   // 3º Copiar a un nuevo array los no repes.
   valores = copyArray(valores, valores.Count - n)
fin funcion


// Recorre con dos bucles, en el primero se marca con 'i' el valor a buscar
//     con el segundo bucle se busca la cantidad de repes que hay para ese valor y
//     se van bajando, así cada repe, es 'tapado', por el que está por encima de él.
//     Al final del array quedarán valores sucios, de haberse bajado 'n' repes, ahí acaba el primer bucle.
//  'j' y 'k' son los índices de recorrido en cada bucle.
//  'n' es la cantidad de repes que se va hallando.
// 'ultimo' es el último actualizado a cada vez que se salga del bucle que localiza repes y baja lo.
entero = Funcion EliminarRepes(array de enteros valores() )
   entero i, j, k, n, u, ultimo

   u = valores.count -1 //el índice mayor del array
   ultimo = (u -1)
   k = 1: j=0
   Hacer mientras (j< ultimo)
       i = valores(j)
       
       si ( valores(k) = i )
           Hacer
               n = (n +1)
               valores(j+n) = valores(k)
               k = (k+1)
           Repetir mientras ((valores(k) = i ) y (k<u))
           ultimo = (valores.ultimo -1 - n)  //actualizamos cual será el último.
       Sino
           valores(j+n) = valores(k)
           k= (k+1)
       Fin si

       j= (j+1)
   siguiente

   devolver n
fin funcion

// Copia a un nuevo array la 'cantidad' de ítems del array valores a un nuevo array
//    se devuelve el array copiado.
array de enteros = copyArray(array de enteros valores(), entero cantidad)
   entero k
   array de enteros sinRepes()
 
   alojar tamaño para sinRepes(0 a cantidad-1)
   bucle para k desde 0 hasta cantidad -1
       sinRepes(k) = valores(k)
   siguiente
   devolver sinrepes
fin funcion


Pasar el código a pseudocódigo, sin cometer errores (y corigiendo algún gazapo que se me haya escapado, cosas de +1, -1, etc... que a veces se escapa al hacerlo de corrido), queda enteramente a tu esfuerzo... lo que te exige entenderlo, no copiar y pegar.

[Beginner Web]

Bueno puede ser que pidas eliminar los que se repiten o conservar valores unicos, eso fue lo que entendi perdon, un ejemplo con caracteres seria este, con numeros es casi lo mismo, cuando encuentras uno repetido haces que todo el arreglo se corra 1 posicion a la izquierda y luego el indicador final decrementa en 1 tambien , eso en cada recorrido.
Mira:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <string.h>

using namespace std;

const int MAX=32;
typedef char tcad[MAX];

void eliminar_repetidos(tcad &c);

int main()
{
tcad palabra="estoy soltera";
eliminar_repetidos(palabra);
cout<<"Palabra modificada: "<<palabra<<endl;
system("pause");
}

/*void eliminar_repetidos(tcad &c)//Este modulo elimina todo lo que se repite
{

int i, j, k, contador;
tcad auxiliar;
strcpy(auxiliar,c);
for(i=0;i<strlen(auxiliar);i++){
contador=0;
for(j=0;j<strlen(auxiliar) && contador<2;j++){
if(auxiliar[i]==auxiliar[j])
contador++;
}
if(contador==1){
c[k]=auxiliar[i];
k++;
}
}
c[k]='\0';
}
*/
//Este otro conserva valores unicos
void eliminar_repetidos(tcad &c)
{
int i, j, k, indice=strlen(c);
tcad auxiliar;
strcpy(auxiliar,c);
for(i=0;i<strlen(auxiliar);i++){
for(j=i+1;j<indice;j++){
if(auxiliar[i]==c[j]){
for(k=j;k<indice;k++)
c[k]=c[k+1];
indice--;
}
}
}
c[indice]='\0';
}

[Serapis]

Ana, aunque tu descripción técnicamente es correcta, es subóptima...
Imagina un array de 1 millón de elementos, entonces tienes que para buscar repes en un millón de elementos, por cada repe hay que mover todos los de encima.
El peor caso sería que todo el array tuviera  un único y mismo valor, lo que implica que el segundo array se ejecutaría la primera vez 1 millon-1, el segundo ciclo 1 millón menos 2, el tercer ciclo un millón menos 3... así hasta que lleguemos al penúlimo el 999998 que solo moveremos 1.

La descripción que yo doy es la misma, pero el movimiento de ítems está optimizado, ninguno se mueve más de 1 vez. Para ello basta llevar adecuadamente actualizado cada índice... De la descripción dada, tan solo varía que al final, se entrega un array con solo los elementos no repetidos, que han sido copiados a un nuevo array, que a fin de cuentas es algo opcional según se necesite o no.

[dijsktra]

El problema es bonito, pero no trivial. Con ánimo constructivo

• La solución de Ana es correcta pero ineficiente, se dice que está en O(n^3) (3 bucles)
• La solucion de NEBIRE tiene ideas aprovechables, porque se requiere ordenar el vector, pero el paso 2 es díficil de seguir con 7 variables, algunas sin inicializar, y _creo_ que está en O(n^2), por los dos bucles. Además creo que se pide eliminar los elementos del vector de entrada, no una opia

La que propongo, ya implementada en C++, requiere ordenar el vector, cosa que se puede hacer con las rutinas de STL, en complejidad O(nlog(n)), y la que hace el proceso de "soltar" los repetidos está en O(n). En total O(nlog(n)) que es mejor que O(n^2).
Fijaos que es muy simple, aunque no tan sencillo de demostrar que sea correcta.

Fijaos en los dibujos que ilustran el invariante y podr'eis ententer como progresa el algoritmo.

Código (cpp) [Seleccionar] Expandir


/*
   P : V=A[0..N)   N>= 0
   fun dropRedundant(V=A[0..N) of int) return M:int
   Q : \forall i : 0 <=  i < N : \exists j :0 <= j < M : A[i]=V[j]
       and
       M = #i : 0 <= i < N : frec(A,0,N,A[i])= 1

   I : Q[N/n] and  0 <= M <= n <= N and
       StrictSorted(V,0,M) and Sorted(V,n,N)

   where

   frec(A,i,j,v) ::= # p : i<= p < j : A[p]=v


   I and B |- Q  (trivial, since n=N)


Snapshot invariant: (Hard)
-------------------

0     1     2    m=3    4     5     6    n=7    8           N
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  3  |   3 |  3  |  3  |  4  |     |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+


*/

#include <iostream>
#include <algorithm> // sort

using namespace std;
// O(n)
int dropRedundant(int V[], const int N)
{
  int m,n;
  sort(V,V+N); // O(nlog(n)
  // V sorted.
  for(n=m=0;n<N;n++) // O(n)
    if (m==0 || V[n]>V[m-1]) V[m++]=V[n];
  return m;
}

#define MAX 10000

int main(int argc, char *args[])
{
  int N,M;
  int V[MAX];
  for ( ; cin >> N; )
    {
      for(int n=0 ; n < N ;  n++ ) cin >> V[n];
      M=dropRedundant(V,N);
      cout << M << endl;
      for(int m=0;m<M;m++) cout << V[m] << " ";
      cout << endl;
    }
}



Algunos ejemplos de entreada. La primera linea  marca el numero de elementos, la segunda el vector a considerar.

Código [Seleccionar] Expandir


6
1 1 2 2 3 3
6
2 2 1 3 4 5
6
2 2 2 2 3 1

En la salida, se da la dimensión del nuevo vector y los elementos originales sin repetir

Código [Seleccionar] Expandir


3
1 2 3
5
1 2 3 4 5
3
1 2 3

Que os sirva!

[Serapis]

dijsktra, creo que no has revisado adecuadamente mi pseudocódigo... está en un tiempo O(n)

El bucle externo, recorre una sola vez cada elemento único, ya que la condición final, se va decrementando en el bucle interno, razón por la que se elige un bucle 'while'.

Si un array tiene pongamos 1000 elementos y hay 250 repes... el bucle externo, primero apunta a 999, pero al final solo habrá llegado hasta al 749. El bucle interno, en cambio solo recorre esos 250 repes, la suma de ambos es pués el total 1000 elementos.
Por supuesto alguna pequeña optimización puede hacerse, quizás eliminando variables, etc... pués está redactado al vuelo...

La declaración de  variables 'no inicializadas', ya te he respondido en alguna ocasión, que en pseudocódigo uno no tiene necesidad de dar detalles que distraigan la atención de lo que se pretende explicar, toda vez que cualquier programador podrá entender sin problemas tales detalles nimios.
Así poner el valor de un número a cero, es innecesario en pseudocódigo, otra cosa es que el valor inicialmente deba ser distinto del valor que tiene por defecto cada tipo de variable... es decir el pseudocódigo se abstrae de las características de todos los lenguajes, porque ya el que aplique algo a su lenguaje u otro aplicará lo que tal o cual lenguaje exija.

[dijsktra]

NEBIRE, me alegro de participar contigo.

Yo también soy partidario de escribir en pseudo-código, máxime cuando este da facilidades que los lenguajes "reales" no ofrecen, como asignación simultánea.... (En este sentido, me encanta más Python) Pero el valor inicial de una variable es algo esencial a tener explícitamente en cuenta.

Tu algoritmo se puede escribir más simple, y eso hace que el programador (no la máquina) lo entienda mejor.

Código [Seleccionar] Expandir


P : sorted(V=A[0..N)
Q : \forall  i : 0 <= i < N : (\exists j : 0 <=j < M : A[i]=V[j])

I : Q[N/n] and 0 <= k <= n <= N and N>n>0 -> V[n]!=V[n-1]
C(n) = N-n >= 0

proc bajarRepes(i/o V=A[0..N) of integer, o k integer )
n,k = 0,0
while n<N do
  V[k],k = V[n],k+1
  n=n+1
  while n<N and V[n]==V[n-1]
     n = n+1
  end
endwhile


Que efecitvamente, esta en O(n), ya que la instrucción crítica (n<N) se ejecuta un máximo de N veces. (Siendo pedantes, también está en O(n^2) , en O(n^56)  )
Erratas tenemos todos... Pero también los ingleses dicen que "el diablo está en los detalles"...

[KrishCM]

Reduciendo un poco lo hecho por el compa del principio:

Código [Seleccionar] Expandir

#include<iostream>
using namespace std;
int main(){
    int vctr[4],vctr_aux[4],vctr_f[4],cnt, k,z=0;
    for(int i=0;i<4;i++){
        cout<<"Ingrese un numero :";
        cin>>vctr[i];
        cnt=0;
        vctr_aux[k]=vctr[i];
        for(k=0;k<i;k++){
             if(vctr_aux[k]==vctr[i]) cnt++;
             }
             if(cnt==1){
                    vctr_f[z]=vctr[i];
                    z++;
            }
    }
    cout<<"Arreglo sin repes"<<endl;
    for(int i=z-1;i>=0;i--){
        cout<<vctr_f[i]<< endl;
    }
    return 0;
}