c++ - 在 C++ 中计算数组中的反转时得到错误的输出

Question

问题是 https://www.geeksforgeeks.org/counting-inversions/

数组的反转计数表示 - 数组距离排序多远（或接近）。如果数组已经排序，则反转计数为 0，但如果数组以相反的顺序排序，则反转计数为最大值。形式上来说，如果 a[i] > a[j] 并且 i < j 两个元素 a[i] 和 a[j] 形成一个反转

阅读文章后，帮助我找出代码中的错误/缺失。我在这里使用了mergeSort 技术。

我的代码是：

#include <vector>
using namespace std;
int merge(vector<int>& nums, int start, int mid, int end){
    int count = 0;
    int n1 = mid - start + 1;
    int n2 = end - mid;
    vector<int> leftArray(n1);
    vector<int> rightArray(n2);
    for(int i = 0; i < n1; i++){
        leftArray[i] = nums[start + i];
    }
    for(int i = 0; i < n2; i++){
        rightArray[i] = nums[mid + 1 + i];
    }
    int i = 0, j = 0, k = start;
    while(i < n1 && j < n2){
        if(leftArray[i] <= rightArray[j]){
            nums[k++] = leftArray[i++];
        }
        else{
            nums[k++] = rightArray[j++];
            count += (mid - i);
        }
    }
    while(i < n1){
        nums[k++] = leftArray[i++];
    }
    while(j < n2){
        nums[k++] = rightArray[j++];
    }
    return count;
}

int mergeSort(vector<int>& nums, int start, int end){
    if(start >= end) return 0;
    int count = 0;
    
    int mid = (start + end) / 2;
    count +=  mergeSort(nums, start, mid);
    count += mergeSort(nums, mid + 1, end);
    count += merge(nums, start, mid, end);
    return count;
}

int countInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
    //return nums;
}

标签： c++arraysalgorithmsortingmergesort