Obtenir les indices d'un tableau après un tri ?

Question

Supposons que l'utilisateur entre un tableau, par exemple :

Array = {France, Spain, France, France, Italy, Spain, Spain, Italy}

dont je connaissais la longueur

le site index le tableau serait :

index = {0, 1, 2, 3, 4, 5, 6, 7}

Maintenant, après l'avoir trié en utilisant Arrays.sort(Array);

newArray sera comme :

newArray = {France, France, France, Italy, Italy, Spain, Spain, Spain}

et le newIndex le sera :

newIndex = {0, 2, 3, 4, 7, 1, 5, 6}

Le problème est le suivant : comment puis-je trouver le newIndex à partir du tableau d'entrée ?

Merci d'avance

Answer 1

Ne pas trier le tableau pour commencer. Triez le tableau d'index, en passant dans un comparateur qui compare les valeurs en les utilisant. comme index dans le tableau. Vous obtenez donc newIndex comme résultat du tri, et il est trivial de passer de là au tableau trié des éléments réels.

Certes, cela signifie qu'il faut trier un tableau d'entiers d'une manière personnalisée - ce qui signifie soit utiliser une fonction Integer[] et la bibliothèque Java standard, ou une bibliothèque tierce qui dispose d'une interface "IntComparator" pouvant être utilisée en conjonction avec une interface sort(int[], IntComparator) type de méthode.

EDIT : Ok, voici un exemple de comparateur. Pour des raisons de simplicité, je vais supposer que vous voulez seulement trier un tableau "original" de chaînes de caractères... et je ne vais pas m'embêter avec le test de nullité.

public class ArrayIndexComparator implements Comparator<Integer>
{
    private final String[] array;

    public ArrayIndexComparator(String[] array)
    {
        this.array = array;
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[array.length];
        for (int i = 0; i < array.length; i++)
        {
            indexes[i] = i; // Autoboxing
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
         // Autounbox from Integer to int to use as array indexes
        return array[index1].compareTo(array[index2]);
    }
}

Tu l'utiliserais comme ça :

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.

Answer 2

Une façon concise d'y parvenir avec l'API Stream de Java 8,

final String[] strArr = {"France", "Spain", "France"};
int[] sortedIndices = IntStream.range(0, strArr.length)
                .boxed().sorted((i, j) -> strArr[i].compareTo(strArr[j]) )
                .mapToInt(ele -> ele).toArray();

Answer 3

TreeMap<String,Int> map = new TreeMap<String,Int>();
for( int i : indexes ) {
    map.put( stringarray[i], i );
}

Maintenant, un itérateur sur map.values() pour récupérer les index dans l'ordre de tri, et sur map.keySet() pour obtenir les chaînes de caractères, ou sur map.entrySet() pour obtenir les String-index-Pairs.

Answer 4

Dans le cas d'un scénario où l'on doit trier de manière répétée des tableaux primitifs de type float ou int avec des valeurs positives, une méthode comme celle ci-dessous permet d'obtenir une vitesse bien meilleure (x3~x4) par rapport à l'utilisation de comparateurs :

long time = System.currentTimeMillis();
for (int i = 0; i < iters; i++) {           
    float[] array = RandomUtils.randomFloatArray(-1,  1, 3000);
    long[] valueKeyPairs = new long[array.length]; 
    for (int j = 0; j < array.length; ++j) {
        valueKeyPairs[j] = (((long) Float.floatToIntBits(array[j])) << 32) | (j & 0xffffffffL);
    }
    Arrays.sort(valueKeyPairs);
    /**Then use this to retrieve the original value and index*/
    //long l = valueKeyPairs[j];
    //float value = Float.intBitsToFloat((int) (l >> 32));
    //int index = (int) (l);
}
long millis = System.currentTimeMillis() - time;

Answer 5

J'ai fait ce qui suit en me basant sur le code de @Skeet. Je pense que c'est un peu plus OOPie. Je ne sais pas.

public static <T extends Comparable<T>> List<Integer> sortIndex(List<T> in) {
    ArrayList<Integer> index = new ArrayList<>();
    for (int i = 0; i < in.size(); i++) {
        index.add(i);
    }

    Collections.sort(index, new Comparator<Integer>() {
        @Override
        public int compare(Integer idx1, Integer idx2) {
            return in.get(idx1).compareTo(in.get(idx2));
        }
    });

    return index;
}

Au lieu que la classe qui implémente le tri et l'indexation ait le code Comparator pour les différents objets entrants, les objets du tableau original doivent implémenter l'interface Comparable. Il semble que de nombreux objets intéressants aient un ordre naturel et que l'interface Comparable soit déjà implémentée.

public static void main(String[] args) {

    List<Integer> a1 = new ArrayList<>(Arrays.asList(2, 3, 9, 4, 1));
    // Just pass in the list to have its indexes sorted by the natural ordering
    List<Integer> idx = sortIndex(a1);

    List<Double> a2 = new ArrayList<>(Arrays.asList(1.0, 5.3, 5.2, -3.1, 0.3));
    idx = sortIndex(a2);

    List<numBits> a3 = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        a3.add(new numBits(i));
    }

    // If you need to sort the indexes of your own object, you must implement
    // the Comparable Interface.
    idx = sortIndex(a3);
}

static class numBits implements Comparable<numBits> {
    private int a;

    public numBits(int i) {
        a = i;
    }

    public String toString() {
        return Integer.toString(a);
    }

    // Sort by the total number of bits in the number.
    @Override
    public int compareTo(numBits that) {
        if (Integer.bitCount(this.a) < Integer.bitCount(that.a))
            return -1;
        if (Integer.bitCount(this.a) > Integer.bitCount(that.a))
            return 1;
        return 0;
    }
}