1

我仍然是编程的初学者，我正在学习在线课程（算法）

练习题之一是计算包含 100000 个随机排序的数字的文件中的反转次数

所以这是我的代码

    package algo_inversion;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Algo_inversion {
    public static int splitMerge(int[]A,int start,int mid,int finish){
        int count=0;
        int []L=new int[mid+2-start];
        int []R=new int[finish-mid+1];
        System.arraycopy(A, start, L, 0, L.length-1);
        L[L.length-1]=5000000;//infinity

        for(int i=0;i<R.length-1;i++){
            R[i]=A[mid+1+i];
        }
        R[R.length-1]=5000000;//infinity

        int x=0;
        int y=0;
        for(int k=start;k<finish+1;k++){
            if(L[x]<=R[y]){
                A[k]=L[x];
                x++;
            }
            else{
                A[k]=R[y];
                y++;
                count+=L.length-1-x;
            }
        }
        return count;        
    }
    public static int countMerge(int []A,int start, int finish){
        if(finish<=start){
            return 0;
        }
        else{
            int mid=(finish+start)/2;
                int leftCount=countMerge(A,start,mid);
                int rightCount=countMerge(A,mid+1,finish);
                int splitCount=splitMerge(A,start,mid,finish);
                return(leftCount+rightCount+splitCount);
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        int []a=new int[100001];
       Scanner in= new Scanner(new FileReader("IntegerArray.txt"));
       int i=0;
        while(in.hasNext()){
            a[i]=in.nextInt();
            i++;
        }
        in.close();
        System.out.println("inversions=: "+countMerge(a, 0, i-1));

    }
}

我在大小从 1 到 200 的随机数组上尝试了它，它工作得很好，但是使用文件中的数组它给了我一个负数！！！我只是不知道是什么原因造成的，如果我能得到任何帮助，我将不胜感激^_^

4

2 回答 2

1

一个大小数组中最坏情况的反转数N是N*(N-1)/2. 适合 int 的最大值大约为 20 亿，因此大小大于 的数组65,000有可能溢出 an int，使结果看起来为负数。

您应该切换到long以扩展计数器可表示的值范围：

public static long splitMerge(int[]A,int start,int mid,int finish) {
    long count = 0;
    ...
}
public static long countMerge(int []A,int start, int finish) {
    ...
}
于 2013-08-04T14:39:52.210 回答
1

我在大小从 1 到 200 的随机数组上尝试了它，它工作得很好，但是使用文件中的数组它给了我一个负数！！！

反转的数量似乎超过了的值，Integer.MAX_VALUE因此您看到溢出为负数；你应该用它long来计算反转的次数。

这是 Joel Spolsky 的The Perils of JavaSchools的一个例子。通过将人们隐藏在机器中的真实情况之外，他们在遇到此类问题时不知道发生了什么。当你在数一些东西时，你看到负面结果，首先应该跳进你脑海的是溢出，超出了Integer.MAX_VALUE.

于 2013-08-04T14:41:56.980 回答