En general, el mayor número posible de inversiones que puede tener una matriz de elementos n es
[matemáticas] (n * (n-1)) / 2 [/ matemáticas]
Entonces, si tiene, por ejemplo, una matriz con 6 elementos, el mayor número posible de inversiones es
[matemáticas] (6 * 5) / 2 = 15 [/ matemáticas]
Este es un tipo de control para su recuento (importante para matrices con gran cantidad de elementos).
Para responder a su pregunta con mayor precisión, a la vez que es simple: escriba la matriz ordenada en la que está contando las inversiones. Puede hacerlo horizontal o verticalmente, según su elección. Luego, debajo o junto a él, escriba esa matriz con elementos invertidos.
- ¿Por qué las matrices tienen una mejor ubicación de caché que la lista vinculada?
- Cómo encontrar la solución más óptima para una pregunta en particular que se ha enviado en LeetCode
- ¿Todos los algoritmos de agrupamiento no están supervisados?
- ¿Puede un gráfico ser un circuito de Euler y una ruta al mismo tiempo?
- ¿Cómo podrías escribir un programa que ingrese un número entero positivo N y genere el número de Fibonacci F2N?
Conecte los mismos elementos de ambas matrices. Cuente las intersecciones totales y allí está su número de inversiones para esa matriz en particular. Algo como esto:
Es fácil ver qué pares están invertidos, solo siga la línea amarilla a través de las uniones: [3,2], [5,2] y [5,4], un total de 3 inversiones.
Ahora, para responder su pregunta con mayor precisión, esta vez haciéndolo complicado:
El algoritmo de clasificación de fusión, por su naturaleza, descubrirá inversiones. Su trabajo es solo establecer el contador de inversión en su código.
Comienza dividiendo la matriz A de 6 elementos dada, ya que la idea de dividir y conquistar funciona. Terminas con dos arreglos B y C. de 3 elementos, aún sin clasificar. Los ordenaré instantáneamente, en aras del espacio, pero si implementas correctamente el algoritmo de clasificación de fusión, deberías seguir dividiendo los arreglos, hasta que termines con n matrices de tamaño 1 (en este ejemplo n = 6).
Entonces, ahora hemos ordenado las matrices B y C [en la línea donde los elementos se volvieron azules]. Podemos comenzar a fusionar matrices ordenadas. En el paso 1 [parte verde de la imagen], tomamos el primer elemento de la matriz B (que es B [0] = 1) y el primer elemento de la matriz C – C [0] = 2 y los comparamos. Comience siempre con la matriz izquierda. Como el elemento de la matriz izquierda es más pequeño, se agregará a la matriz resultante D como elemento D [0]. Es aburrido cuando el elemento de la matriz izquierda es más pequeño, no pasa nada con el contador de inversión.
Terminado con B [0]. Índice de incremento para la matriz B. Ahora estamos mirando B [1] (paso verde 2). Compare B [1] = 3 con C [0] = 2. Tenga en cuenta que el índice para la matriz C sigue siendo 0. No lo incrementa hasta que se convierta en miembro de la matriz D resultante. Ahora es interesante. B [1] es mayor que C [0] (ya que 3> 2), por lo que 2 se agrega a D como miembro D [1]. Ocurre una cosa más: incrementa su contador de inversión, como siempre lo hace cuando el miembro de la matriz izquierda es mayor que el miembro de la matriz derecha. Ahora tienes 1 inversión. Pero, dado que las matrices B y C ya están ordenadas (recuerde), y le queda un miembro más en la matriz B (es el número 5), ese miembro debe ser mayor que el miembro anterior (número 3), por lo que significa que eso el miembro también es mayor que C [0]. Y de hecho, no es necesario compararlos, simplemente incremente el contador de inversión por el número de elementos restantes en la matriz B (eso es 1). Ahora tiene 2 inversiones, [3,2] y [5,2].
Paso verde 3: Incremente C [0] a C [1], compare B [1] a C [1]. 3 es menor que 4, por lo que 3 desciende a D, como D [2]. Aburrido.
Paso verde 4: Incremente B [1] a B [2], compare B [2] con C [1]. 5 es mayor que 4, así que, nuevamente, sucede algo interesante. Incrementa su contador de inversión en 1 y ahora tiene 3 inversiones: [3,2], [5,2] y [5,4], como hemos visto en la primera imagen. No tiene más miembros en la matriz B, por lo que no se produce ningún incremento adicional en el contador de inversión. El número 4 baja a D como D [3].
Paso verde 5: Incrementar C [1] a C [2]. Compare B [2] con C [2]. 5 es menor que 6, entonces 5 baja a D como D [4]. Aburrido.
Paso verde 6: El último miembro C [2] permanece. No se hicieron comparaciones. 6 baja a D y se convierte en D [5].
Fin del algoritmo.
