Инверсия в массиве a
размера n
называется парой (i,j)
для которого он держит это i<j
а также a[i]>a[j]
, Я пытаюсь реализовать функцию в C ++, которая подсчитывает количество инверсий в данном массиве. Я следовал подходу «разделяй и властвуй», который просто модифицирует алгоритм сортировки слиянием и выполняется за O (n log n) времени. Вот мой код до сих пор:
long long int glob;
template< class T >
long long int merge( T *arr, int beg, int mid, int end ) {
queue< int > left;
queue< int > right;
for( int i=beg; i<=mid; ++i ) {
left.push( arr[i] );
}
for( int i=mid+1; i<=end; ++i ) {
right.push( arr[i] );
}
int index=beg;
int ret=0;
while( !left.empty() && !right.empty() ) {
if( left.front() < right.front() ) {
arr[index++] = left.front();
left.pop();
} else {
arr[index++] = right.front();
right.pop();
ret+=left.size();
}
}
while( !left.empty() ) { arr[index++]=left.front();left.pop(); }
while( !right.empty() ) { arr[index++]=right.front();right.pop(); }
return ret;
}
template< class T >
void mergesortInvCount( T *arr, int beg, int end ) {
if( beg < end ) {
int mid = (int)((beg+end)/2);
mergesortInvCount( arr, beg, mid );
mergesortInvCount( arr, mid+1, end );
glob += merge( arr, beg, mid, end );
}
}
Для некоторых тестовых случаев это дает правильные результаты, но для некоторых других это дает мне неправильный вывод. Я неправильно понял алгоритм или допустил ошибку при реализации? Может ли кто-нибудь помочь мне? Заранее спасибо.
Test case: 2 1 3 1 2
Correct: 4
Mine: 6
Я не проверил все шаги в вашем коде, но ваша строка
if( left.front() < right.front() )
предложите мне, что в else-ветке «ret» увеличивается не только когда a (j)> a (i), но и когда они равны, что не соответствует вашему описанию случая. Поэтому, возможно, вам следует попытаться изменить строку, приведенную выше, на:
if( left.front() <= right.front() )
С уважением
Тест
if( left.front() < right.front() )
должно быть <=
, Теперь вы перемещаете идентичные значения из правой половины в ячейку из левой половины, считая инверсии, которых нет (каждое такое вхождение учитывает ложные инверсии числа идентичных предметов в левом). В вашем примере вы должны дублировать пары, каждая из которых создает одну фантомную инверсию.