Discussion :

[CompuTux]

Bonjour,

Etant donné un tableau T de N nombres entiers positifs, j'aimerais écrire le programme qui le tasse, c'est-à-dire qui détecte les éléments nuls du tableau et qui récupère leur place en décalant vers le début du tableau tous les autres éléments.

Evidemment, le programme que j'ai écrit ne marche pas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package exoalgo;
import java.util.Random;
/**
 *
 * @author cbohnert
 */
public class Exo34 {
 
    public static void main(String[] args) {
 
     int tab[]=new int[10];
     int x=0;
 
     Random randomGenerator = new Random();
     for (int i=0; i<=tab.length-1;i++) { tab[i]= randomGenerator.nextInt(5); System.out.print(tab[i]+",");}
     System.out.println();
 
     for (int i=1;i<=tab.length-1;i++) {
 
         if (tab[i]==x) {
 
            tab[i]=tab[i+1]; 
         }
 
     }
 
     for (int i=0; i<=tab.length-1;i++) {System.out.print(tab[i]+","); }
     System.out.println();
     System.out.println(tab.length);
    }
 
 
 
}

J'obtiens pour un essai :

init:
deps-jar:
compile-single:
run-single:
2,3,1,1,2,2,2,1,0,3,
2,3,1,1,2,2,2,1,3,3,
10
BUILD SUCCESSFUL (total time: 0 seconds)

C'est-à-dire que les zéros sont bien enlever mais il y a répétition de l'élément successeur ...

Quelqu'un pourrait-il m'expliquer svp ??

[Nudger]

Bonsoir,

Tout d'abord, lorsque tu rencontre la valeur vide: if (tab[i]==x) { ...
N'est déplacé que l'élément suivant.
Il faut faire une seconde boucle for qui part de i et qui va jusqu'à la fin du tableau pour déplacer tout les éléments après i.

Par ailleurs, lorsque le tableau change de taille, il n'y a pas d'autre moyen que de créer un nouveau tableau; on ne peut pas changer la taille d'une tableau dynamiquement.

[rtg57]

Bonjour,

puisqu'il faut faut réallouer de la mémoire lors du "tassement" du tableau, ne serait-il pas intéressant de parcourir le tableau initial, à la recherche d'élément valides, puis de créer un nouveau tableau dans lequel on copierait ces éléments ?

Ou peut être travailler avec une classe ArrayList...

En espérant que cela vous aide...

[akkai]

Je valide il vaut mieu travailler avec une arraylist
Tu parcours ton tableau et à chaque valeur non null (!=0) tu l'ajoute dans ta liste.

Si tu as absolument besoin de tableau d'entier, rien de t'empêche de recréer un nouveau tableau à partir de ta liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

maListe.toArray();

[Alkhan]

bonjour,
Je pense pas que travailler avec une arrayList soit une bonne solution d'un point de vue performance.
Je verais plutot les choses comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
  int taille = tab.length; // on garde la taille car celle ci va évoluer en cours de route.
  ..... // code de recherche des valeurs à supprimer
  // pour chaque valeur trouvé on fait ce qui suit
  int index = // l'index de la valeur à supprimer.
  int nbDepl = taille - index -1;
  if (nbDepl > 0) {
    System.arraycopy(tab, index+1, tab, index, nbDepl); // déplacement des données stocké après l'index
  }
   tab[--taille] = 0; // affectation sur la dernière cellule vidée

[le y@m's]

bonjour,
Je pense pas que travailler avec une arrayList soit une bonne solution d'un point de vue performance.
Je verais plutot les choses comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
  int taille = tab.length; // on garde la taille car celle ci va évoluer en cours de route.
  ..... // code de recherche des valeurs à supprimer
  // pour chaque valeur trouvé on fait ce qui suit
  int index = // l'index de la valeur à supprimer.
  int nbDepl = taille - index -1;
  if (nbDepl > 0) {
    System.arraycopy(tab, index+1, tab, index, nbDepl); // déplacement des données stocké après l'index
  }
   tab[--taille] = 0; // affectation sur la dernière cellule vidée

Je ne pense pas que faire une recopie de tableau à chaque élément supprimé soit une bonne solution non plus pour les performances (le nombre de copie de tableau augmente avec le nombre de zero présents dans le tableau original ).

Je propose de créer un deuxième tableau de même taille que le premier, on y copie les entiers différents de 0 tout en comptant leur nombre puis enfin on crée le tableau final de bonne longueur et on y copie tous les éléments non nuls.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
int[] tempTab = new int[tab.length];
int index = 0;
for(int value : tab) {
    if(value != 0) {
        tempTab[index ++] = value;
    }
}
int[] noZeroTab = new int[index];
System.arraycopy(tempTab, 0, noZeroTab, 0, index);

[Alkhan]

+1 le y@m's je suis d'accord !

Mon idée était surtout de garder le même tableau, et .... je plaide coupable, je suis parti du principe le son tableau ne sera pas beaucoup plus grand.

[Chatanga]

Remarques en passant :

• Pour afficher un tableau, Arrays.toString(monTableau) ;
• une ArrayList utilise un tableau en interne (d'où son nom), rendant l'accès à une cellule rapide ;
• on peut implémenter cet algo tout simple sans tout recopier à chaque 0 rencontré, il suffit de déplacer chaque cellule de N où N est le nombre de 0 précédement rencontrés.