24 votes

Tri appariés tableaux en Java

Disons que j'ai deux tableaux (en Java),

int[] nombres; et int[] couleurs;

Chaque iième élément de chiffres correspond à sa i-ème élément en couleurs. Ex, numéros = {4,2,1} couleurs = {0x11, 0x24, 0x01}; Signifie que le numéro 4 est de couleur 0x11, le nombre 2 est 0x24, etc.

Je veux trier les numéros de tableau, mais encore il a de sorte que chaque élément correspond à la paire en couleurs.

Ex. nombres = {1,2,4}; couleurs = {0x01,0x24,0x11};

Quelle est la plus propre, la plus simple façon de le faire? Les tableaux ont quelques milliers d'éléments, afin d'être en place serait préférable, mais pas nécessaire. Serait-il judicieux de faire un Tableaux.sort() et une coutume de comparaison? À l'aide des fonctions de la bibliothèque, autant que possible, est préférable.

Note: je sais que la meilleure solution est de faire une classe pour les deux éléments et utiliser un comparateur. Cette question vise à demander aux gens de la façon la plus rapide de ce code. Imaginez-vous être à une programmation de la concurrence, vous ne voulez pas faire de toutes ces classes, les classes anonymes pour le comparateur, etc. Encore mieux, oubliez Java; comment voulez-vous code en C?

20voto

tovare Points 1896

Vous pouvez utiliser de tri() avec un comparateur si vous avez gardé un troisième tableau avec l'index, et triés sur, le laissant données intactes.

Exemple de code Java:

Integer[] idx = new Integer[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;              
Arrays.sort(idx, new Comparator<Integer>() {
    public int compare(Integer i1, Integer i2) {                        
        return Double.compare(numbers[i1], numbers[i2]);
    }                   
});

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

Notez que vous devez utiliser Integer au lieu de int ou vous ne pouvez pas utiliser un comparateur.

8voto

Frank Pape Points 685

Il semble que le plus propre chose à faire serait de créer une propriété personnalisée classe qui implémente Comparable. Par exemple:

class Color implements Comparable {
  private int number;
  private int color;

  // (snip ctor, setters, etc.)

  public int getNumber() {
    return number;
  }
  public int getColor() {
    return color;
  }

  public int compareTo(Color other) {
    if (this.getNumber() == other.getNumber) {
      return 0;
    } else if (this.getNumber() > other.getNumber) {
      return 1;
    } else {
      return -1;
    }
  }
}

Vous pouvez séparer votre algorithme de tri à partir de la logique de commande (vous pouvez utiliser des Collections.type si vous utilisez une Liste au lieu d'un tableau), et plus important encore, vous n'aurez pas à vous soucier d'une certaine manière l'obtention de deux tableaux de la synchronisation.

4voto

finrod Points 1138

Si vous seriez prêt à consacrer un peu d'espace supplémentaire, vous pouvez générer un autre tableau, l'appeler supplémentaire, avec des éléments comme ceci:

extra = [0,1,...,numbers.length-1]

Ensuite, vous pouvez trier les extra ce tableau à l'aide de Tableaux.sort() avec la coutume de référence (qui, tout en comparant les éléments i et j compare vraiment les numéros supplémentaires[i]] et les chiffres[extra[j]]). De cette façon, après le tri de la matrice extra, extra[0] contiendra l'indice du plus petit nombre et, comme les nombres et les couleurs ne bougent pas, la couleur correspondante.
Ce n'est pas très joli, mais il fait le travail, et je ne peux pas vraiment penser à un moyen plus facile de le faire.

Comme une note de côté, dans la compétition, j'ai l'habitude de trouver le C++ basé sur un modèle de paires et de nice cartes indispensable ;)

3voto

JeffFoster Points 354

Pourquoi ne pas introduire un objet pour représenter un nombre et d'une couleur et de mettre en œuvre un comparateur de fonction pour ça?

Aussi, avez-vous vraiment besoin d'un tableau, pourquoi ne pas utiliser quelque chose provenant de la Collection?

3voto

Paul Tomblin Points 83687

J'aime @tovare de la solution. Faire un tableau de pointeurs:

int ptr[] = { 1, 2, 3 };

et puis, quand vous triez sur les nombres, les permuter les valeurs du ptr au lieu de chiffres. Puis accès par le biais du ptr tableau, comme

for (int i = 0; i < ptr.length; i++)
{
   printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]);
}

Mise à jour: ok, il apparaît d'autres dois me battre pour cela. Pas d'XP pour moi.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X