5

私は現在、マージソートを使用して反転演習を数えることに取り組んでいます。私が直面している問題は、小規模または中規模の配列がある場合、結果は完全に問題ありませんが、非常に大きなテストケース (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

何か案は？あらゆる種類の助けをいただければ幸いです。ありがとうございました。

編集:整数オーバーフローのケースについての回答で述べたように、オーバーフローを引き起こす変数「カウント」が「ロング」として初期化されるため、理解するのに苦労しています。この場合、オーバーフローはありません。私のコードで整数オーバーフローを引き起こす他の変数は考えられません。どうもありがとう。

アップデート：

整数オーバーフローに関連する問題はありませんでしたが、回答に感謝しますが、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

32 ビット整数に収まらない数値を使用しているため、オーバーフローが発生しています。long2^63 より小さい結果に使用するか、メモリに収まるすべての可能な整数にjava.math.BigIntegerを使用します。

于 2013-07-10T23:07:27.150 に答える
2

より大きい数値を格納しようとしています-代わりにInteger.MAX_VALUEa を使用してみてくださいlong

于 2013-07-10T23:04:37.430 に答える
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 に答える