java - 查找反转次数

Question

以下是一个算法，该算法应该使用归并排序查找数组中的反转次数。它会产生错误的输出，虽然它非常简单，但我看不出它有什么问题。你能帮帮我吗？

例如，对于输入1 3 3 1 2，即对于perm。 (3 1 2) 它产生 39994，而不是 2。

/* *
 * INPUT:
 * 1. t : number of test cases; t test cases follow
 * 2. n : number of elements to consider in each test case
 * 3. ar[i] : n numbers, elements of considered array
 * */

import java.util.*;

public class Inversions {

    // Merges arrays left[] and right[] into ar[], returns number of
    // inversions found in the process
    public static long merge(long[] arr, long[] left, long[] right) {
        int i = 0, j = 0;
        long count = 0;
        while (i < left.length || j < right.length) {
            if (i == left.length) {
                arr[i+j] = right[j];
                j++;
            } else if (j == right.length) {
                arr[i+j] = left[i];
                i++;
            } else if (left[i] <= right[j]) {
                arr[i+j] = left[i];
                i++;                
            } else {
                arr[i+j] = right[j];
                // # inv. is curr. size of left array
                count += left.length-i;
                j++;
            }
        }
        return count;
    }

    // Traditional merge sort on arr[], returns number of inversions
    public static long invCount(long[] arr) {
        if (arr.length < 2)
            return 0;

        int m = (arr.length + 1) / 2;
        long left[] = Arrays.copyOfRange(arr, 0, m);
        long right[] = Arrays.copyOfRange(arr, m, arr.length);

        return invCount(left) + invCount(right) + merge(arr, left, right);
    }

    public static void main (String args[]) {
        int t, n;
        long[] ar = new long[20000];
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        while(t-- > 0) {
            n = sc.nextInt();
            for(int i = 0; i < n; i++) {
                ar[i] = sc.nextLong();
            }
            System.out.println(invCount(ar));
        }
    }
}

我知道我不是第一个问类似问题的人。我可以找到正确的算法。我只是好奇这个有什么问题。

谢谢!

Answer 1

问题是您计算的不是长度为 n 而是长度为 20000 的数组中的反转次数，由零扩展。解决方法是使数组大小合适:

public static void main(String args[]) {
    int t, n;
    Scanner sc = new Scanner(System.in);
    t = sc.nextInt();
    while (t-- > 0) {
        n = sc.nextInt();
        long[] ar = new long[n];
        for (int i = 0; i < n; i++) {
            ar[i] = sc.nextLong();
        }
        System.out.println(invCount(ar));
    }
}