Obtener los índices de una matriz después de la clasificación?

Question

Supongamos que el usuario introduzca una matriz, por ejemplo:

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

que Yo sé lo largo de ella

la matriz index sería:

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

Ahora, después de la clasificación usando Arrays.sort(Array);

newArray será como:

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

y la newIndex será:

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

El problema es: ¿cómo puedo encontrar el newIndex de la matriz entrada?

Gracias de antemano

Answer 1

No ordenar la matriz para empezar. Ordene la matriz de índice, pasando un comparador que compara los valores al usarlos como índices en la matriz. Así que terminas con newIndex como resultado de la clasificación, y es trivial ir desde allí a la matriz ordenada de elementos reales.

Es cierto que significa ordenar una matriz de enteros de una manera personalizada - que o bien consiste en utilizar un Integer[] y la biblioteca estándar de Java, o una biblioteca de 3 ª parte que tiene una interfaz "IntComparator" que puede ser usado en conjunción con un sort(int[], IntComparator) tipo de método

EDITAR: Bien, aquí hay un ejemplo de comparador. En aras de la simplicidad, supongo que solo desea ordenar una matriz "original" de cadenas ... y no me molestaré con la prueba de nulidad.

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]); 
    } 
} 

Se podría utilizar de esta manera:

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

Una forma de poder hacer esto es envolver el índice original y el nombre del país en una clase separada. Luego ordena la matriz según los nombres. De esta manera, se conservarán sus índices originales.

Answer 3

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

Ahora iterador sobre map.values ​​() para recuperar los índices en orden de clasificación, y más de map.keySet() para obtener las cadenas, o sobre map.entrySet() para obtener la cadena de índice pares .

Answer 4

¿Qué es lo primero vistazo es el mapa de ellos de esa

Map <Integer, String> map = new HashMap<Integer, String>(); 
map.put(0, "France"); 
map.put(1, "Spain"); 
map.put(2, "France"); 

y luego ordenarlos por valor like that y luego se puede saber sus índices y valores (clave, valores) acaba de imprimir el mapa

Iterator mapIterator = map.keySet().iterator(); 

while (mapIterator .hasNext()) { 
    String key = mapIterator.next().toString(); 
    String value = map.get(key).toString(); 

    System.out.println(key + " " + value); 
} 

Answer 5

forma concisa de lograr esto con la API de Java 8 Stream,

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 6

Hice lo siguiente basado en el código de @Skeet.Creo que es un poco más OOPie. No se.

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; 
} 

En lugar de la clase que implementa la clasificación e indexación que tiene el código de comparación para los diferentes objetos que entran, los objetos de la matriz original, debe implementar la interfaz Comparable. Parece que muchos objetos de interés tienen un orden natural y ya tienen implementada la interfaz Comparable.

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; 
    } 
} 

Answer 7

Si tener un escenario de clasificación repetidamente flotador primitivo o arrays int con valores positivos, a continuación, un método como debajo de los rendimientos mucho mejor (x3 ~ x4) velocidad en comparación con el uso de cualquier comparadores:

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;