Todos los desafíos
Difícil 1 resuelto 100.0% de aceptación

Count Inversions

Count the out-of-order pairs in a list.

Lo que aprenderás

  • Contar pares desordenados durante la mezcla
  • Ampliar merge sort con un conteo
  • Pasar de O(n²) a O(n log n)

Problema

An inversion is a pair of positions i < j with numbers[i] > numbers[j]. Count all inversions. Lists can be long, so a merge-sort based O(n log n) count is needed.

Implement count_inversions(numbers).

Input

numbers: The list of integers.

Output

Return the number of inversions.

Restricciones

0 ≤ length ≤ 200,000

Ejemplos

Ejemplo 1
Entrada:
numbers = [2, 4, 1, 3, 5]

Salida esperada:
expected = 3
Entrada:
std::vector<long long> numbers = {2, 4, 1, 3, 5};

Salida esperada:
long long expected = 3;
Entrada:
long[] numbers = new long[] {2, 4, 1, 3, 5};

Salida esperada:
long expected = 3;

Explicación

Out-of-order pairs: (2,1), (4,1), (4,3): 3 inversions.

Ejemplo 2
Entrada:
numbers = [1, 2, 3]

Salida esperada:
expected = 0
Entrada:
std::vector<long long> numbers = {1, 2, 3};

Salida esperada:
long long expected = 0;
Entrada:
long[] numbers = new long[] {1, 2, 3};

Salida esperada:
long expected = 0;

Explicación

Already sorted: 0 inversions.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Una inversión se cuenta cuando un número del lado izquierdo sigue siendo mayor que uno del lado derecho durante la mezcla.

Pista 2

Divide la lista recursivamente y cuenta los pares cruzados mientras mezclas mitades ordenadas.

Pista 3

Ten cuidado con los duplicados: los valores iguales no son inversiones, así que importa la dirección de la comparación.

Complejidad esperada

tiempo O(n log n), espacio extra O(n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 970 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.