Cómo calcular el número de inversiones en una lista que contiene números sin clasificar que oscilan entre 1 y 100,000

Answer 1

El siguiente código espera una matriz entera como argumento y devuelve el número de pares de inversión en él.

Utiliza casi la misma lógica que el tipo de fusión.
Complejidad espacial: O (N)
Complejidad de tiempo: O (NlogN)

InversionFinder clase pública <T extiende Comparable > {

@SuppressWarnings (“sin marcar”)
public long countInversions (entrada T []) {
int bajo = 0;
int high = input.length – 1;

T [] temp = (T []) new Comparable [input.length];
System.arraycopy (input, 0, temp, 0, input.length);

T [] aux = (T []) new Comparable [input.length];

return countAndSort (input, temp, aux, low, high);
}

private long countAndSort (T [] left, T [] right, T [] aux, int low, int high) {
inversiones largas = 0;
if (alto == bajo)
devuelve 0;
si (alto <bajo) {
lanzar nueva IllegalArgumentException (“Parámetros incorrectos pasados”);
}
int mid = low + (high-low) / 2;
inversiones = inversiones + countAndSort (izquierda, derecha, auxiliar, baja, media);
inversiones = inversiones + countAndSort (izquierda, derecha, auxiliar, medio + 1, alto);
inversiones = inversiones + fusión (derecha, auxiliar, baja, alta, media);
inversiones de retorno;
}

combinación larga privada (T [] arr, T [] aux, int low, int high, int mid) {
inversiones largas = 0;

// copia todos los elementos de la matriz principal a la matriz auxiliar
para (int k = bajo; k <= alto; k ++) {
aux [k] = arr [k];
}
// índice inicial de subarreglos izquierdos ordenados
int i = bajo;
// índice inicial de la submatriz derecha ordenada
int j = mid + 1;

para (int k = bajo; k <= alto; k ++) {
// fin de la primera parte
if (i> mid) {
arr [k] = aux [j ++];
}
// fin de la segunda parte
más si (j> alto) {
arr [k] = aux [i ++];
}
// si aux [i] es más pequeño que aux [j]
si no (menos (aux [i], aux [j])) {
arr [k] = aux [i ++];
}
// si aux [j] es más pequeño que aux [i], esto significa que hay inversiones
más {
arr [k] = aux [j ++];
long leftArrUnIteratedCount = (mid – i + 1);
inversiones = inversiones + leftArrUnIteratedCount;
}
}
inversiones de retorno;
}

privado booleano menos (T a, T b) {
return (a.compareTo (b) <0);
}

public static void main (String [] args) {
InversionFinder inversionFinder = nuevo InversionFinder ();
Entero [] arr = {1,3,5,2,4,6};
System.out.println (inversionFinder.countInversions (arr));
}
}

Answer 2

Mientras explora la lista, almacene todos los elementos en un árbol equilibrado donde cada nodo almacene el tamaño de su subárbol. Para cada elemento de la lista, agregue el número de elementos ya vistos que son mayores que él al número total de inversiones. Esto le brinda la solución en n * log (n) tiempo (técnicamente O (n) ya que el número de nodos en el árbol está limitado por 100,000 si los valores repetidos se almacenan en el mismo nodo).