计数在尺寸<code>n</code>的阵列<code>a</code>反转以阵列C++

反演的数量，被称为对(i,j)对于其认为i<j和a[i]>a[j]。我试图在C++中实现一个函数，它计算给定数组中的反转次数。我遵循分而治之的方法，它只是修改合并排序算法，并在O（n log n）时间运行。这是我到目前为止的代码：计数在尺寸<code>n</code>的阵列<code>a</code>反转以阵列C++

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

来源

2012-10-10 Rontogiannis Aristofanis

你能不能学会使用调试器-e.g. 'gdb'-来调试你的程序（你可能想用Linux上的'g ++ -Wall -g'编译它）。 –

你有没有为我们提供更具体的错误描述（如测试用例和预期的和实际的（不正确的）结果）？ – Grizzly

@Grizzly对不起，编辑。 –

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

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

建议我，在其他分支“RET”是不是只有当（J）增加>一（i），而且当它们是平等的，这不符合你对案件的描述。因此，也许你应该尝试改变上面引述入行：

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

问候

来源

2012-10-10 19:08:44

测试

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

应该<=。现在，您从右半部分开始移动相同的值，然后计算不是的倒数（每个这样的出现计数相同项数左误寄生倒数）。在你的例子中，你必须复制对，每个创建一个幻像反转。

来源

2012-10-10 19:02:17

计数在尺寸<code>n</code>的阵列<code>a</code>反转以阵列C++

回答

相关问题