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
Entrada:
numbers = [2, 4, 1, 3, 5]
Salida esperada:
expected = 3Entrada:
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.
Entrada:
numbers = [1, 2, 3]
Salida esperada:
expected = 0Entrada:
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.