c++ - 实现合并排序代码时无法计算所有反转

Question

我一直在试图弄清楚如何让这段代码来计算所有反转，但似乎无法具体说明。据我了解，这段代码应该计算所有的反转，但它失败了许多测试用例，在正确的方向上轻推，甚至整个修复将受到赞赏。

代码:

int countInversion(vector<int>& v, int& inv) {
    if(v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size()/2);
        vector<int> right(v.begin() + v.size()/2, v.end());

        countInversion(left, inv);
        countInversion(right, inv);

        int l = 0; int r = 0;

        for(int i = 0; i < v.size(); i++) {
            if(r >= right.size() || (l < left.size() && left[l] < right[r])) {
                v[i] = left[l++];
            } else {
                if(right[r] < left[l]) inv += left.size() - l;
                v[i] = right[r++];  
            } 
        }
    } return inv;
}

确实有效的代码(我在互联网上找到的)具有非常低的 可读性有人可以帮助我理解它吗？更重要的是，请指出我的代码到底遗漏了什么，以及是否可以纠正我的代码以正确计数？谢谢!

代码2:

long long ans = 0;

void mergei(int a[],int i,int j) {
    int ni = ((i+j)/2) + 1, nj = j + 1;
    int s = i;
    int* arr = new int [j - i + 1];
    j = ni;
    int k = 0;

    while(i < ni && j < nj) {
        if(a[i] <= a[j]) {
            arr[k] = a[i++];
        } else {
            arr[k] = a[j++];
            ans += (ni - i);
        } k++;
    }

    for(; i < ni; i++, k++) arr[k] = a[i];
    for(; j < nj; j++, k++) arr[k] = a[j];
    for(k = 0; s < nj; s++, k++) a[s] = arr[k];
    delete [] arr;
}

void m_sort(int a[],int i,int j) {
    if(i < j) {
        m_sort(a, i, (i+j)/2);
        m_sort(a, ((i+j)/2) + 1, j);
        mergei(a, i, j);
    }
}

Answer 1

我终于找到了一种使用我的代码来解决它的方法，我确信对 if else 进行了一些更改 block 或者我如何添加反转会修复它，它只是必须，这就是合并排序的全部要点，这就是为什么我坚持以这种方式解决它，而不是仅仅使用另一个代码。问题是；我在做left[l] < right[r]如果它是向左或向右合并，这并不重要，但对于反转却很重要，只需将其更改为 left[l] <= right[r] .

long countInversions(vector<int>& arr, long& inv) {
    if(arr.size() > 1) {
        vector<int> left(arr.begin(), arr.begin() + arr.size()/2);
        vector<int> right(arr.begin() + arr.size()/2, arr.end());

        countInversions(left, inv);
        countInversions(right, inv);

        int l = 0; int r = 0;

        for(int i = 0; i < arr.size(); i++) {
            if(r >= right.size() || (l < left.size() && left[l] <= right[r])) {
                arr[i] = left[l++];
                // inv += r;
            } else {
                arr[i] = right[r++];
                inv += left.size() - l;
            }
        }
    } return inv;
}

稍微好一点、更易读的代码是:

long countInversions(vector<int>& v) {
    if(v.size() <= 1) return 0;

    vector<int> left(v.begin(), v.begin() + v.size()/2);
    vector<int> right(v.begin() + v.size()/2, v.end());

    long inv = countInversions(left) + countInversions(right);

    int l = 0, r = 0;

    for(int i = 0; i < v.size(); i++) {
        if(r >= right.size() || (l < left.size() && left[l] <= right[r])) {
            v[i] = left[l++];
            // inv += r;
        } else {
            v[i] = right[r++];
            inv += left.size() - l;
        }
    }     
    return inv;
}