5

我目前正在使用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”，因此在这种情况下应该没有溢出。我想不出任何其他会在我的代码中导致整数溢出的变量。非常感谢。

更新：

没有与整数溢出相关的问题，但感谢您的回答，但是 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++];
    }

}
4

4 回答 4

2

您正在尝试存储大于Integer.MAX_VALUE- 尝试使用 along代替

于 2013-07-10T23:04:37.430 回答
2

您正在使用不适合 32 位整数的数字，因此存在溢出。用于long小于 2^63 的结果或java.math.BigInteger用于适合您记忆的所有可能整数。

于 2013-07-10T23:07:27.150 回答
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;

    }
于 2013-07-11T09:55:37.810 回答
0

想一想：假设您在 low=99990 和 high=99999 的子数组上调用 sort()。然后中间= 99994。在 merge3CountInvs() 中，nArr1Elems 是什么？"i" 的取值范围是多少？什么将被添加到报表中

       count=count+(nArr1Elems-i);

?

于 2013-07-11T00:03:51.087 回答