求逆序的个数

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的数组中的反转次数，并将其扩展为0。修复方法是使数组的大小合适:

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));
    }
}