Nota: Esta solución calcula la inversión para una matriz. Para calcular las inversiones de dos matrices diferentes, vea mi comentario a continuación.
- Combine la matriz de clasificación A y cree una copia (matriz B)
- Tome A [1] y encuentre su posición en la matriz B ordenada mediante una búsqueda binaria. El número de inversiones para este elemento será uno menor que el número índice de su posición en B ya que cada número menor que aparece después del primer elemento de A será una inversión.
2a. acumule el número de inversiones para contrarrestar la variable num_inversions.
2b. eliminar A [1] de la matriz A y también de su posición correspondiente en la matriz B - vuelva a ejecutar desde el paso 2 hasta que no haya más elementos en A.
Aquí hay un ejemplo de ejecución de este algoritmo. Matriz original A = (6, 9, 1, 14, 8, 12, 3, 2)
1: fusionar ordenar y copiar en la matriz B
B = (1, 2, 3, 6, 8, 9, 12, 14)
2: Tome A [1] y búsqueda binaria para encontrarlo en la matriz B
A [1] = 6
B = (1, 2, 3, 6 , 8, 9, 12, 14)
6 está en la cuarta posición de la matriz B, por lo tanto, hay 3 inversiones. Sabemos esto porque 6 estaba en la primera posición en la matriz A, por lo tanto, cualquier elemento de menor valor que aparezca posteriormente en la matriz A tendría un índice de j> i (ya que i en este caso es 1).
2.b: Eliminar A [1] de la matriz A y también de su posición correspondiente en la matriz B (se eliminan los elementos en negrita).
A = ( 6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)
3: Vuelva a ejecutar desde el paso 2 en las nuevas matrices A y B.
A [1] = 9
B = (1, 2, 3, 8, 9, 12, 14)
9 ahora está en la quinta posición de la matriz B, por lo tanto, hay 4 inversiones. Sabemos esto porque 9 estaba en la primera posición en la matriz A, por lo tanto, cualquier elemento de menor valor que aparezca posteriormente tendría un índice de j> i (ya que i en este caso es nuevamente 1). Eliminar A [1] de la matriz A y también de su posición correspondiente en la matriz B (se eliminan los elementos en negrita)
A = ( 9 , 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 8, 9 , 12, 14) = (1, 2, 3, 8, 12, 14)
Continuar en esta línea nos dará el número total de inversiones para la matriz A una vez que se complete el ciclo.
El paso 1 (clasificación de fusión) tomaría O (n * log n) para ejecutarse. El paso 2 se ejecutaría n veces y en cada ejecución realizaría una búsqueda binaria que lleva a O (log n) a ejecutarse para un total de O (n * log n). El tiempo total de ejecución sería O (n * log n) + O (n * log n) = O (n * log n)
Ver aquí Contando inversiones en una matriz
- ¿Cómo recomienda Foursquare las sugerencias de mis amigos de Facebook?
- Cómo implementar un algoritmo de equilibrio de carga personalizado aparte del algoritmo Round Robin predeterminado en mi Amazon Elastic Load Balancer usando Java SDK para AWS
- ¿Cuál es la diferencia entre array estático y automático?
- ¿Por qué ocurre el peor de los casos en Max-Heapify cuando la fila final del árbol está medio llena?
- ¿Es CodeChef la opción correcta para practicar problemas algorítmicos hoy en día?
