0

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
4

2 回答 2

2

我没有检查您代码中的所有步骤，但您的行

if( left.front() < right.front() )

向我建议，在 else 分支中，“ret”不仅在 a(j)>a(i) 时增加，而且在它们相等时也会增加，这与您对案例的描述不符。因此，也许您应该尝试将上面引用的行更改为：

if( left.front() <= right.front() )

问候

于 2012-10-10T19:08:44.190 回答
1

考试

if( left.front() < right.front() )

应该是<=。您现在将相同的值从右半部分移到左半部分之前，计算不存在的反转（每次出现这种情况都会计算左侧相同项目的数量）虚假反转。在您的示例中，您必须复制对，每对都创建一个幻像反转。

于 2012-10-10T19:02:17.590 回答