gpt4 book ai didi

c++ - 计算数组中的反转次数,C++

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:47:48 25 4
gpt4 key购买 nike

数组反转 a尺寸n称为一对(i,j)为此它认为i<ja[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() )

问候

关于c++ - 计算数组中的反转次数,C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12825579/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com