Newsgroup: it.comp.lang.c
Titolo: trova doppi in un vettore di numeri

Ciao a tutti
c'č qualcuno che mi potrebbe spiegare come fare per cercare se in un vettore
compare piů di una sola volta un numero e mi restituisca il numero dei
numeri che compaiono una volta sola?
grazie in anticipo
saluti
V

in linguaggio C naturalmente :)

 
A me sembra un esercizio o qualcosa di simile, quindi e' meglio che te 
la fai da solo la codifica in c. Poi non e' nemmeno molto chiara la 
prima parte della domanda: vuoi vedere se "un numero qualunque" compare 
piu' di una volta o intendi un numero specifico? Comunque qui c'e' un aiuto:
.
.
.
.
.
.
.
.
.
.
.
.
.
int num_unici(int *vett, int dim_vett)
{
   int u;  /*numeri unici*/
   int q;  /*occorrenze del numero*/
   int i,j;
   u=0;
   for(i=0;i<dim_vett;i++){
	  vett[i];
           q=0;
	  for(j=0;j<dim_vett;j++){
		  if(vett[j]==vett[i])
			  q++;
	  }
	  if(q==1){     /*una sola occorrenza del num corrente*/
		  u++;  /*aumenta il contatore*/
	  }
   }
return u;
}
-- 
Devaraja (Xdevaraja87^gmail^c0mX)
Linux Registerd User #338167
http://counter.li.org

 }
si, qua il tempo e' O(n^2) [(per n^2 intendo n*n)]
si potrebbe fare in tempo O(n*log n) sfruttando qsort:
<QUOTE>
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int compare(const void *arg1, const void *arg2)
{
    const int a1 = *(const int*)arg1;
    const int a2 = *(const int*)arg2;
    return (a1<a2)?-1:((a1>a2)?+1:0);
}
int main()
{
    /* vettore di input */
    int v[] = {7,4,9,6,8,3,7,4,1,0,2,3,8,5};
    /* variabili usate dall'algoritmo */
    int sorted[sizeof(v)/sizeof(int)];
    int i = 0;
    int unique_counter = 0;
    /* rendiamo sorted una copia di v */
    memcpy(sorted,v,sizeof(v));
    /* ordiniamo sorted con qsort */
    qsort(sorted,sizeof(v)/sizeof(int),sizeof(int),compare);
 
    /* estrapoliamo numeri che appaiono una sola volta */
    for(i=0;i<sizeof(v)/sizeof(int);++i){
        if((i+1)<(sizeof(v)/sizeof(int))){
            if(sorted[i]!=sorted[i+1]){
                /**/printf("%d e' unique\n",sorted[i]);
                ++unique_counter;
            }
            while(sorted[i]==sorted[i+1]){
                /**/printf("%d NON e' unique\n",sorted[i]);
                ++i;
            }
            }else{
                /**/printf("%d e' unique\n",sorted[i]);
                ++unique_counter;
            }
    }
    /* stampa numero di numeri che appaiono una volta sola */
    printf("Ci sono %d numeri che compaiono una sola
volta!\n",unique_counter);
    return 0;
}
</QUOTE>
<OUTPUT>
0 e' unique
1 e' unique
2 e' unique
3 NON e' unique
4 NON e' unique
5 e' unique
6 e' unique
7 NON e' unique
8 NON e' unique
9 e' unique
Ci sono 6 numeri che compaiono una sola volta!
</OUTPUT>
Commentando le righe con /**/ (debug info) si ottiene solo:
<OUTPUT>
Ci sono 6 numeri che compaiono una sola volta!
</OUTPUT>
se ad uno non interessa perdere il contenuto di v puo' anche chiamare
qsort su v stesso (invece che su sorted) risparmiandosi il tempo per la
copia.
qsort ha tempo n*log n, la copia ha tempo lineare e cosi' pure il ciclo
finale dopo il sort che conta quanti siano i numeri unici:
n + n*log n + n. Quindi O(n*log n).
Per set di numeri abbastanza grandi e' sicuramente parecchio piu'
veloce, per set di numeri piccoli invece no.
Con un vettore di 100.000 numeri la versione con qsort ci mette molto
meno di un decimo di secondo metre la versione O(n*n) ci impiega 12
secondi.
Detto questo pero', la versione O(n*n) con set di numeri molto piccoli
(ad esempio 10 numeri) dovrebbe essere piu' veloce.
Concludo dicendo che se il set di numeri che il vettore puo' contenere
avesse certe proprieta' particolari si potrebbe scrivere algoritmi
ancora piu' veloci.
Ad esempio se contenesse solo numeri nel range 0..99 si potrebbe creare:
int count[100] = {0};
scorrere v e per ogni iterazione fare: ++count[v[i]];
alla fine si scorre count e si stampano/contano tutti gli i dove
count[i] == 1;
questo richiederebbe:
tempo n per scorrere l'array e comporre count[]
tempo r per scorrere count (in questo caso r e' 100, r e' il range).
Insomma tempo lineare!
Siamo passati da:
O(n*n)
a
O(n*log n)
a
O(n)
Se tutto questo ti sembra arabo (parlo con colui che ha postato il primo
messaggio) e cercavi invece una funzione che fa tutto da sola... mi
spiace informarti ma il C ha una libreria piuttosto ristretta!
Tommaso
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 
Naturalmente, se l'intervallo dei valori possibili è noto ed è 
sufficientemente limitato è possibile identificare i doppioni in un tempo 
O(n).
Max

 wrote 


Si, ovvio. Se avevi la pazienza di leggere il mio post fino in fondo
avresti notato che parlavo anche di questo:
<MEGA CUT>
Concludo dicendo che se il set di numeri che il vettore puo' contenere
avesse certe proprieta' particolari si potrebbe scrivere algoritmi
ancora piu' veloci.
Ad esempio se contenesse solo numeri nel range 0..99 si potrebbe creare:
int count[100] = {0};
scorrere v e per ogni iterazione fare: ++count[v[i]];
alla fine si scorre count e si stampano/contano tutti gli i dove
count[i] == 1;
questo richiederebbe:
tempo n per scorrere l'array e comporre count[]
tempo r per scorrere count (in questo caso r e' 100, r e' il range).
Insomma tempo lineare!
Siamo passati da:
O(n*n)
a
O(n*log n)
a
O(n)
</MEGA CUT>
;-)
Ora, il mio post era molto lungo e per questo credo sia stato positivo
ri-tirare fuori questo concetto grazie al tuo post.


 int count[100] = {0};
Nel caso specifico dell'OP, giacché serviva soltanto identificare i valori 
non ripetuti, possiamo riservare un solo bit di informazione per ogni 
valore possibile, riducendo la dimensione dell'array a (max-min)/8 byte.
Se sizeof(int) vale 4, con 512MB di RAM possiamo applicare il procedimento 
a un array di int con valori qualsiasi. :)
Max