[java] sfida algoritmica

[Lucked]

L'algoritmo che vi propongo di creare deve eliminare gli elementi ripetuti in un array di interi ordinato.

esempio :

2,2,2,2,5,8,8,9,10

diventa:

2,5,8,9,10

Io sono arrivato da solo a una soluzione ma non ve la pongo per non influenzarvi. Credo comunque che ce ne siano altre e forse più semplici.



P.S: non si può fare uso di array aggiuntivi e si possono usare solo 2 indici...l'array prende un array e restituisce un int della nuova posizione scrivibile

[keratox]

int x,z,y;
for(x=0;x<nomearray.length;x++){
if(x==0){
z=nomearray[x]; // ultimo valore
}
else{
if(z==nomearray[x]){
/* Attenzione,il valore e' uguale al precedente */
/* operazioni necessarie alla cancellazione dell'elemento in posizione x */
}
else{
z=nomearray[x]; //ultimo valore diverso
}
}
}

l'algoritmo te lo presento sotto codice

[Lucked]

Noo! :bubu: :bubu: come..operazioni necessarie per.....
nooooooo! :tongue: dai...prova a farlo e se funziona scrivi

fallo in versione metodo.
il metodo deve avere come parametro l'array e restituire un int della nuova posizione scrivibile, visto che l'array sarà piu piccolo

[anx721]

int  compact(int[] array){
    int i = 0;
    int j = 0;
    while(j < array.length){
          if(array[j] != array[i]){
                i++;
                array[i] = array[j];     
           }
           j++;
    }
    return i++;
} 

[Lucked]

si proprio cosi, ma l'avevi gia visto o l'hai inventato adesso? Dai..non ci credo, l'avevi almeno gia visto :bubu:

ci deve essere qualche piccolo errore però...l'ho provato cosi:

class abc{
  public static void main(String[] arg){
    int[] array = {1,1,5,5,5,5,8,9,10,10};

    int cont = eliminaOccorrenze(array);

    for(int i=0;i<cont;i++) System.out.println(array[i]);

  }


public static int eliminaOccorrenze(int[] array){
    int i = 0;
    int j = 0;
    while(j < array.length){
          if(array[j] != array[i]){
                i++;
                array[i] = array[j];
           }
           j++;
    }
    return i++;
}
}

[anx721]

Cavolo, sai qual era l'errore (eraltro individuato subito :adhone: )

return i++;

con quest'espressione prima viene eseguito il return e poi i viene incrementato, per cui veniva ritornato il valore corretto meno 1. Quindi basta fare:
return ++i;

public static int eliminaOccorrenze(int[] array){
    int i = 0;
    int j = 0;
    while(j < array.length){
          if(array[j] != array[i]){
                i++;
                array[i] = array[j];
           }
           j++;
    }
    return i++;
} 

PS: non l'avevo già visto :sexpulp: ... d'altro canto ti pare un problema difficile? Era piu difficile quello dell'altra volta...

[Angelo1974]

Ciao a tutti. Volendo, possiamo utilizzare una cosa orientata più agli oggetti; ecco la mia soluzione ( sfruttando che nei Set di Java le ripetizioni non sono ammesse ); potrebbe essere meno performante delle vostre però c'è da dire che segue un po' la logica degli oggetti. Ciao a tutti

public class Example {

  public void eliminaOccorrenze( int[] a ){
    Set set = new HashSet();
    for( int i = 0; i < a.length; i++ ){

      set.add( new Integer( a[i] ) );
    }
    Iterator iteratore = set.iterator();
    while( iteratore.hasNext() ){

      System.out.println( ( ( Integer )( iteratore.next() ) ).intValue() );
    }
  }

  public static void main( String args[] ){

    int[] array = {

        1,1,2,2,3,4,5,6,2,4,7
    };
    new Example().eliminaOccorrenze( array );
  }
} 

[Xadoom]

Alternativamente utilizzando un array di boolean per memorizzare i numeri già usciti.

class abc{
    
  static int[] ordinato;  
  static int[] array = {1,1,5,5,5,5,8,9,10,10};
  
  public static void main(String[] arg){
    eliminaOccorrenze(array);
    for(int i=0;i<array.length;i++) System.out.println(ordinato[i]);
  }


public static void eliminaOccorrenze(int[] array){
   boolean[] presente;
   presente = new boolean[11];
   ordinato = new int[array.length];
   int j=0;

   for(int i=0;i<10;i++){presente[i]=false;}
   
   for(int i=0;i < array.length;i++){
     if(!presente[array[i]]){
         ordinato[j] = array[i];
         presente[array[i]] = true;
         j++;
        }
   }
 }
}

[anx721]

Ciao a tutti. Volendo, possiamo utilizzare una cosa orientata più agli oggetti; ecco la mia soluzione ( sfruttando che nei Set di Java le ripetizioni non sono ammesse ); potrebbe essere meno performante delle vostre però c'è da dire che segue un po' la logica degli oggetti. Ciao a tutti

Il metodo non rispetta le specifiche: non compatta gli elementi nell'aray e non ritorna l'indice della prima posizione disponibile :quote:

però c'è da dire che segue un po' la logica degli oggetti

Gli oggeti si usano per altre cose...

Quanto alla soluzione di Xadoom poi...anche questa non rispetta le specifiche, ma poi è praticamente inutilizzabile: se il mio array contiene numeri arbitrariamente grandi, 1000, 2000, 10000, che fai ti allochi un array di 10000 elementi?

[Lucked]

be' complimenti. La mia soluzine era un po' più lunga :bubu:
la cosa che mi fa riflettere, è questa: che se capisci come funziona il mio algoritmo e come funziona l'altro(vedi quello di Anx) gli indici si spostano in modo molto molto simile. Penso che sia proprio la mia idea più difficile(nel senso che occorrono piu istruzioni) da realizzare. ad esempio io confronto sempre l'elemento precedente all'indice di ricerca e non mi era proprio venuta l'idea che bastava usare l'altro indice che restava fermo :bubu: Sembra se ci pensate, anche curioso che ci siano 2 soluzioni diverse per risolvere questo problema, per questo l'ho proposto nel forum :metallica

class EliminaOccorrenze{
  public static void main(String[] arg){
    int[] array = {1,1,5,5,5,5,8,9,10,10};

    int cont = eliminaOccorrenze(array);
    if(cont==-1) cont = array.length;
    for(int i=0;i<cont;i++) System.out.println(array[i]);

  }


/*
  1caso: 1155555
        15|55555      superato
  2caso: 113456
        13456|6       superato
  3caso: 135578
        13578|8       superato
  4caso: 1355788
        13578|88      superato
  5caso: 13456
         13456        superato(return -1)
*/

  public static int eliminaOccorrenze(int[] a){
    int i=1, pointer;


    while(i<a.length && a[i] != a[i-1]) i++;

    if(i<a.length && a[i] == a[i-1]) {

      pointer = i+1;
      while(pointer<a.length) {
        if(a[pointer]==a[pointer-1]) pointer++;
        if(pointer<a.length) {
          if(a[pointer]!=a[pointer-1]) {a[i] = a[pointer]; i++; pointer++;}
        }
      }
    }
  //la distinzione viene fatta per capire se sono stati cancellati valori ripetuti
  if(i==a.length) return -1; else return i;}


}