Count Inversions

Q: ¿Qué es una inversión en un array?

Una inversión es un par de posiciones i < j donde nums[i] > nums[j] , así que un valor mayor aparece antes que uno menor. Una lista ordenada tiene 0 inversiones, y una lista invertida de valores distintos tiene la mayor cantidad: n(n-1)/2 . El recuento equivale al número de intercambios entre elementos vecinos que realiza el ordenamiento de burbuja.

Q: ¿Cuál es la complejidad temporal de contar inversiones con merge sort?

Tiempo O(n log n) y espacio adicional O(n) para el búfer de fusión. Cada uno de los log n niveles de fusión recorre cada valor una vez, unos 3 × 10^5 pasos para 2 × 10^4 valores. El bucle por pares es O(n²) .

MedioOrdenación Recursión

+10

Dada una lista de enteros nums, devuelve el número de inversiones: pares de índices i < j con nums[i] > nums[j], es decir, un valor mayor antes que uno menor. Los valores iguales nunca forman una inversión, y una lista ordenada no tiene ninguna.

Función

countInversions(nums: integer-array) → integer

numsinteger-array: la lista de números enteros
Devuelveinteger: el número de pares i < j con nums[i] > nums[j]

Restricciones

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
La respuesta es como máximo n(n-1)/2 < 2 × 10⁸, así que cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: nums = [5, 3, 8, 1, 4]
Salida: 6
Explicación: 5 va antes que 3, 1 y 4: 3 pares. 3 va antes que 1, y 8 antes que 1 y 4: 3 más. 1 y 4 están en orden, así que el total es 6.

Para ir más allá

¿Qué cambia si un par solo cuenta cuando nums[i] > 2 × nums[j]? ¿Puede la ordenación por mezcla seguir contando esos pares en O(n log n)?

Solución

Comprobar cada par requiere aproximadamente n² / 2 comparaciones. La ordenación por mezcla cuenta los pares en bloque: cuando se coloca un valor de la mitad derecha durante una mezcla, todos los valores de la izquierda que aún están esperando son mayores y aparecieron antes que él. Una resta cuenta todo ese grupo, así que el recuento no cuesta nada más que la ordenación O(n log n).

Comprueba cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

Para cada índice i, comprueba cada índice posterior j y suma 1 cuando nums[i] > nums[j]. Esa es la definición, y la comparación estricta excluye los valores iguales.

El coste es de n(n-1)/2 comparaciones: casi 2 × 10^8 para 2 × 10^4 valores, y duplicar n lo hace cuatro veces mayor.

Algoritmo

Establece count = 0.
Para cada i desde 0 hasta n-1, y cada j desde i + 1 hasta n-1, suma 1 a count cuando nums[i] > nums[j].
Devuelve count.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Ordenamiento por mezcla que cuenta mientras combina

Intuición

Divide la lista por la mitad. Una inversión tiene ambos valores en la mitad izquierda, ambos en la derecha o uno a cada lado. La recursión en cada mitad cuenta los dos primeros tipos y ordena esa mitad. La ordenación mueve los valores solo dentro de una mitad, así que cada valor de la izquierda sigue estando antes que cada valor de la derecha, y los pares cruzados no cambian.

En la mezcla, si left[i] ≤ right[j], coloca left[i]: todos los valores de la derecha que siguen esperando son al menos tan grandes como right[j], así que no forman ninguna inversión. De lo contrario, right[j] es menor que left[i] y, como la mitad izquierda está ordenada, menor que todos los valores de la izquierda que siguen esperando. Suma su cantidad. Colocar el valor de la izquierda en caso de empate mantiene fuera los valores iguales.

En [5, 3, 8, 1, 4], las mitades contienen 1 y 2 inversiones. Al mezclar [3, 5] con [1, 4, 8], 1 pasa por delante de 3 y 5, y 4 pasa por delante de 5: 1 + 2 + 3 = 6.

Algoritmo

Copia nums y crea un búfer de la misma longitud.
Para ordenar y contar un rango de menos de 2 valores, devuelve 0.
En caso contrario, divídelo en mid y ordena y cuenta cada mitad.
Fusiona las mitades usando el búfer: si se cumple left[i] ≤ right[j], toma el valor de la izquierda; en caso contrario, toma el valor de la derecha y suma el número de valores de la izquierda que aún no se han colocado.
Copia el rango fusionado de vuelta y devuelve la suma de los tres recuentos.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

Errores comunes y casos límite

Sumar 1 cuando se coloca un valor de la derecha. Este pasa por delante de todos los valores de la izquierda que siguen esperando, así que suma su cantidad, mid - i.
Tomar el valor de la derecha en caso de empate, usando left[i] < right[j] como condición para el lado izquierdo. Después, [2, 2, 2, 1] cuenta los 2 iguales entre sí y devuelve más de 3. Usa ≤.
Contar mientras se copian los elementos restantes después de que se agoten los valores de una mitad. Los valores restantes de la izquierda no tienen ningún valor de la derecha después de ellos, y los valores restantes de la derecha ya se compararon con todos los valores de la izquierda.

Preguntas frecuentes3

¿Qué es una inversión en un array?

Una inversión es un par de posiciones i < j donde nums[i] > nums[j], así que un valor mayor aparece antes que uno menor. Una lista ordenada tiene 0 inversiones, y una lista invertida de valores distintos tiene la mayor cantidad: n(n-1)/2. El recuento equivale al número de intercambios entre elementos vecinos que realiza el ordenamiento de burbuja.

¿Cuál es la complejidad temporal de contar inversiones con merge sort?

Tiempo O(n log n) y espacio adicional O(n) para el búfer de fusión. Cada uno de los log n niveles de fusión recorre cada valor una vez, unos 3 × 10^5 pasos para 2 × 10^4 valores. El bucle por pares es O(n²).

¿Se pueden contar las inversiones sin usar ordenamiento por mezcla?

Sí. Un árbol de Fenwick (árbol indexado binario) sobre los rangos de los valores recorre la lista una vez y, para cada valor, pregunta cuántos valores anteriores son mayores, en O(log n) por valor. Eso también es O(n log n) en total. Un árbol de búsqueda balanceado que registra los tamaños de los subárboles funciona de la misma manera.

def countInversions(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [5, 3, 8, 1, 4]

Salida Esperada