¿Cómo encontrar el número de inversiones en una matriz?

Question

Duplicar posible:
Counting inversions in an array

Ésta es una phone interview question: "Encontrar el número de inversiones en una matriz". Supongo que se refieren a la solución O (N log N). Creo que no puede ser mejor que O (N log N) ya que esta es la complejidad de clasificación.

Las respuestas a un similar question se pueden resumir de la siguiente manera:

1. Calcular la mitad de la distancia que los elementos deben ser movidos para ordenar la matriz: copiar la matriz y ordenar la copia. Para cada elemento de la matriz original a[i] encuentre su posición j en la copia ordenada (búsqueda binaria) y sume las distancias a la mitad abs(i - j)/2.

2. Modificar merge sort: merge modificar para contar las inversiones entre los dos conjuntos ordenados y ejecutar regularmente con merge sort que merge modificado.

   ¿Tiene sentido? ¿Hay otras soluciones (quizás más simples)? ¿No es demasiado difícil para una entrevista telefónica?

Answer 1

En realidad, es una aplicación del algoritmo de divide y vencerás, y si usted está familiarizado con ella se puede llegar a la solución rápidamente.

Tome [1 3 8 5 7 2 4 6] como ejemplo, suponga que hemos ordenado una matriz como [1 3 5 8] y [2 4 6 7], y ahora tenemos que combinar las dos matrices y obtener el número de inversiones totales.

Dado que ya tenemos el número de inversiones en cada subarreglo, solo tenemos que averiguar el número de inversiones causadas por la combinación de matrices. Cada vez que se inserta un elemento, por ejemplo, 2 insertado en [1 # 3 5 8], puede saber cuántas inversiones hay entre la primera matriz y el elemento 2 (3 pares en este ejemplo). Luego puede agregarlos para obtener el número de inversiones causadas por la fusión.

Answer 2

También es posible usar un enfoque de conteo tipo similar, si la matriz contiene sólo un pequeño número, por ejemplo (como si se trata de una matriz de caracteres):

inversions = 0 
let count = array of size array.Length 
for i = 0 to array.Length - 1 do 
    for j = array[i] + 1 to maxArrayValue do 
     inversions = inversions + count[j] 

    count[array[i]] = count[array[i]] + 1 

Básicamente, mantener un recuento de cuántas veces cada elemento aparece. Luego, en cada paso i, el número de inversiones que genera el elemento i th es igual a la suma de todos los elementos mayores que i que aparecen antes de i, que puede calcular fácilmente utilizando el recuento que conserva.

Esto será O(n*eps) donde eps es el dominio de los elementos de su matriz.

Esto es definitivamente más simple en mi opinión. En cuanto a la eficiencia, es bueno si eps es pequeño, obviamente. Si es así, entonces debería ser más rápido que otros enfoques ya que no hay recursión.