计数反转(大输入问题)

Question

我目前正致力于使用mergesort计算反演练习.我面临的问题是当我有小型或中型数组时,结果非常好,但是如果我使用一个非常大的测试用例(一个100,000个整数的数组),它就不会给我正确的反转次数.我不知道为什么会发生这种情况.这是我的代码:

static int [] helper;
static long count=0;
static Integer [] arr3;

private static void mergeSortMethod(Integer[] arr3) {
    int head=0;
    int tail=arr3.length-1;
    int mid=tail+((head-tail)/2);

    sort(arr3,head,tail);
}


private static void sort(Integer[] arr3, int low, int high) {

    if (high<=low){
        return;
    }
    int mid=low+ ((high-low)/2);

    sort(arr3,low,mid);
    sort(arr3,mid+1,high);

    merge3CountInvs(arr3,low,mid,high);

}

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) {
    int i=low;
    int j=mid+1;
    int k=low;
    //to get size of first half of array
    int nArr1Elems=(mid-low)+1;

    for (int m=low;m<=high;m++){
        helper[m]=arr3[m];

    }

    while(i < mid+1 && j < high+1){// neither array empty
        if( helper[i] < helper[j] ){
            arr3[k++] = helper[i++];

        }

        else if ( helper[j] < helper[i] ){
            arr3[k++] = helper[j++];
            int numOFElements=nArr1Elems-i;
            count=count+(nArr1Elems-i);

        }
    }
    while(i < mid+1){ // arrayB is empty,
        arr3[k++] = helper[i++];
    }

    while(j < high+1){ // arrayA is empty,
        arr3[k++] = helper[j++];
    }

}

我的解决方案在不使用非常大的输入时提供了正确的答案,但是当我使用100,000个整数的测试用例时,我获得的反转次数是:

从我的实施:-30588581433

正确答案是:2407905288

有任何想法吗？我会很感激任何帮助.谢谢.

编辑:正如关于整数溢出情况的答案中提到的那样,我很难理解,因为导致溢出的变量"count"被初始化为"long",因此在这种情况下应该没有溢出.我想不出任何会在我的代码中导致整数溢出的变量.非常感谢.

更新:

没有与Integer溢出有关的问题,但感谢答案,但是Reddy的回答确实指向了正确的方向,所以再次感谢.我的算法中唯一的错误是:

int nArr1Elems=(mid-low)+1; 

count=count+(nArr1Elems-i); 

什么时候应该是:

count=count+(mid-i+1); 

因为我们必须从数组左侧的元素中"减去"排序,而不是最初在调用子程序时,因为索引在排序后会发生变化.我正在编写我的更新代码以防其他人最终遇到与我类似的问题:

static int [] helper;
static long count=0;
static Integer [] arr3;

private static void mergeSortMethod(Integer[] arr3) {
    int head=0;
    int tail=arr3.length-1;
    int mid=tail+((head-tail)/2);

    sort(arr3,head,tail);
}


private static void sort(Integer[] arr3, int low, int high) {

    if (high<=low){
        return;
    }
    int mid=low+ ((high-low)/2);

    sort(arr3,low,mid);
    sort(arr3,mid+1,high);

    merge3CountInvs(arr3,low,mid,high);

}

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) {
    int i=low;
    int j=mid+1;
    int k=low;

    for (int m=low;m<=high;m++){
        helper[m]=arr3[m];

    }

    while(i < mid+1 && j < high+1){// neither array empty
        if( helper[i] < helper[j] ){
            arr3[k++] = helper[i++];

        }

        else if ( helper[j] < helper[i] ){
            arr3[k++] = helper[j++];
         //to increment count with total number of elements left in arrayA after sorting
            count=count+(mid-i+1);

        }
    }
    while(i < mid+1){ // arrayB is empty,
        arr3[k++] = helper[i++];
    }

    while(j < high+1){ // arrayA is empty,
        arr3[k++] = helper[j++];
    }

}

Answer 1

我的代码对您的数据运行良好，并且得到了完全正确的结果。请与它进行比较并检查你的算法做错了什么

    public static void main(String[] args){
            int[] dataInv = new int[100000];
            Random rand = new Random();
            for (int i = 0; i < dataInv.length; i++) {
                dataInv[i] = rand.nextInt();
            }

            System.out.println("Inversions: " + numberOfInversions(dataInv));
    }

   private static long numberOfInversions(int[] data) {
        int[] temp = new int[data.length];
        return mergeSort(data, temp, 0, data.length - 1);
    }

    private static long mergeSort(int[] data, int[] temp, int low, int high) {
        long inversions = 0L;
        if (high > low) {

            int mid = (high + low) / 2;

            inversions = mergeSort(data, temp, low, mid);
            inversions += mergeSort(data, temp, mid + 1, high);

            inversions += merge(data, temp, low, mid + 1, high);
        }

        return inversions;
    }

    private static long merge(int[] data, int[] temp, int low, int mid, int high) {
        int i, j, k = 0;
        long invertions = 0L;

        i = low;
        j = mid;
        k = low;

        while (i <= (mid - 1) && j <= high) {
            if (data[i] <= data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];

                invertions += (mid - i);
            }
        }

        while (i <= (mid - 1)) {
            temp[k++] = data[i++];
        }

        while (j <= high) {
            temp[k++] = data[j++];
        }

        for (i = low; i <= high; i++) {
            data[i] = temp[i];
        }

        return invertions;

    }