O (n log n) время, O (n) пространство решения в Java.
Слияние, с настройкой для сохранения количества инверсий, выполненных на этапе объединения. (для хорошо объясненного слияния взгляните на http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html)
Поскольку сортировка слиянием может быть выполнена на месте, сложность пространства может быть увеличена до O (1).
При использовании этого вида инверсии происходят только на этапе слияния и только тогда, когда мы должны поместить элемент второй части перед элементами из первой половины, например,
объединено с
у нас есть 3 + 2 + 0 = 5 инверсий:
- 1 с {5, 10, 15}
- 6 с {10, 15}
- 22 с {}
После того, как мы сделали 5 инверсий, наш новый объединенный список
0, 1, 5, 6, 10, 15, 22 * 1031 *
На Codility есть демонстрационная задача ArrayInversionCount, где вы можете протестировать свое решение.
public class FindInversions {
public static int solution(int[] input) {
if (input == null)
return 0;
int[] helper = new int[input.length];
return mergeSort(0, input.length - 1, input, helper);
}
public static int mergeSort(int low, int high, int[] input, int[] helper) {
int inversionCount = 0;
if (low < high) {
int medium = low + (high - low) / 2;
inversionCount += mergeSort(low, medium, input, helper);
inversionCount += mergeSort(medium + 1, high, input, helper);
inversionCount += merge(low, medium, high, input, helper);
}
return inversionCount;
}
public static int merge(int low, int medium, int high, int[] input, int[] helper) {
int inversionCount = 0;
for (int i = low; i <= high; i++)
helper[i] = input[i];
int i = low;
int j = medium + 1;
int k = low;
while (i <= medium && j <= high) {
if (helper[i] <= helper[j]) {
input[k] = helper[i];
i++;
} else {
input[k] = helper[j];
// the number of elements in the first half which the j element needs to jump over.
// there is an inversion between each of those elements and j.
inversionCount += (medium + 1 - i);
j++;
}
k++;
}
// finish writing back in the input the elements from the first part
while (i <= medium) {
input[k] = helper[i];
i++;
k++;
}
return inversionCount;
}
}