【InversionCount逆順対数+MergeSort】
1373 ワード
Definition of Inversion: Let (A[0], A[1] ... A[n], n <= 50) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A. Example:
Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
考え方brute forceを使えばO(n^2)は,マージソートの中のマージステップの考え方を借りる.
Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
考え方brute forceを使えばO(n^2)は,マージソートの中のマージステップの考え方を借りる.
import java.util.Arrays;
public class MergeSort {
static int InversionCount = 0;
public static void main(String[] args) {
int[] array = {3,1,2,5,4,7,6};
MergeSort(array, 0, array.length-1);
System.out.println(InversionCount);
System.out.println(Arrays.toString(array));
}
public static void MergeSort(int[] array, int lhs, int rhs) {
if (lhs < rhs) {
int mid = lhs + ((rhs - lhs)>>1);
MergeSort(array, lhs, mid);
MergeSort(array, mid+1, rhs);
Merge(array, lhs, mid, rhs);
}
}
public static void Merge(int[] array, int lhs, int mid, int rhs) {
int[] tmp = new int[rhs-lhs+1];
int i = lhs, j = mid+1;
int k = 0;
while(i <= mid && j <= rhs)
{
if (array[i] > array[j]) {
InversionCount += mid-i+1;
tmp[k++] = array[j++];
}
else {
tmp[k++] = array[i++];
}
}
while(i <= mid)
{
tmp[k++] = array[i++];
}
while(j <= rhs)
{
tmp[k++] = array[j++];
}
for (i = 0; i < k; i++) {
array[i+lhs] = tmp[i];
}
tmp = null;
}
}