反转计数给出错误的输出

Question

下面的程序是用来数数的。数组中的反转。它给我错误的输出，无法调试代码？对于输入数组：arr[]= { 3,1,2 } 输出：3 但是对于排序后的输入数组，它给出了正确的答案？

#include <iostream>

using namespace std;

int merge_inversion( unsigned long long int* A, long int l, long int m,  
                                                          long int r ){

    int i= l, j= m;
    int inv_count= 0;

    while( i <= m-1 && j <= r ){

        if( A[i] <= A[j] ){
            i++;
        }else{

            j++;
            inv_count+= m-i;
        }
    }

    return inv_count;
 }


unsigned long long int inversion_count( unsigned long long int* A, long  
                                int start, long int end ){

    int mid, inv_count= 0;
    if( start < end ){

        mid= (start + end)/2;

        inv_count= inversion_count( A, start, mid );
        inv_count+= inversion_count( A, mid+1, end );

        inv_count+= merge_inversion( A, start, mid+1, end );

    }

    return inv_count;
}

int main(){

    long int T;
    cin >> T;

    while( T-- ){
        cout << endl;

        long int N;
        cin >> N;

        unsigned long long int *arr= new unsigned long long int[N];
        for( int i=0; i<N; i++ )
            cin >> arr[i];

        cout << inversion_count( arr, 0, N-1 );

        cout << endl;
    }

}

Answer 1

问题出在您的这部分代码中：

while( i <= m-1 && j <= r ){

    if( A[i] <= A[j] ){    //You only count the inversions, but forgot to sort the array.
        i++;
    }else{
        j++;
        inv_count+= m-i;
    }
}

对于排序问题，我们应该创建一个临时数组来存储临时排序结果。

这是一个有效的程序。和你的相似。

#include <iostream>
using namespace std;

int g_nCount;
void mergearray(unsigned long long int* a, int first, int mid, int last, unsigned long long int* temp)
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n) 
    {
        if (a[i] < a[j])
            temp[k++] = a[i++];     //Sorting and counting
        else
        {
            temp[k++] = a[j++];
            g_nCount += m - i + 1;
        }
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++) //Save sorting result to the orginal array.
        a[first + i] = temp[i];
}

void mergesort(unsigned long long int* a, int first, int last, unsigned long long int* temp)
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //Left
        mergesort(a, mid + 1, last, temp); //Right
        mergearray(a, first, mid, last, temp); //Merge
    }
}

bool MergeSort(unsigned long long int* a, int n)
{
    unsigned long long int *p = new unsigned long long int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    return true;
}

int main(){
    long int T;
    cin >> T;

    while( T-- ){
        cout << endl;

        long int N;
        cin >> N;

        unsigned long long int *arr= new unsigned long long int[N];
        for( int i=0; i<N; i++ )
            cin >> arr[i];
        g_nCount = 0;
        MergeSort(arr, N);
        cout << g_nCount << endl;       
    }
}

反转计数给出错误的输出

Inversion Count gives wrong output

c++

sorting

algorithm

mergesort