1

我试图找出任何数组中的反转数。我已经应用了归并排序。在合并子数组时，如果右子数组的任何值小于左子数组的任何值，我都会计算数量。如果数组包含大量数据，则此代码不起作用。

private static long getNumberOfInversions(int[] a, int[] b, int left,
                int right)
{
    long numberOfInversions = 0;
    if (right > left)
    {
        int ave = (left + right) / 2;
        numberOfInversions = getNumberOfInversions(a, b, left, ave);
        numberOfInversions += getNumberOfInversions(a, b, ave + 1, right);
        numberOfInversions += merge(a, b, left, ave + 1, right);
    }
    return numberOfInversions;
}

public static long merge(int[] a, int b[], int left, int ave, int rigth)
{
    int i = 0, j = left, k = ave;
    long count = 0;
    while (j <= ave - 1 && k <= rigth)
    {
        if (a[j] <= a[k])
        {
            b[i] = a[j];
            i++;
            j++;
        }
        else
        {
            b[i] = a[k];
            count += ave - j;
            i++;
            k++;
        }
    }
    while (j <= ave - 1)
    {
        b[i] = a[j];
        i++;
        j++;

    }
    while (k <= rigth)
    {
        b[i] = a[k];
        i++;
        k++;
    }
    while (left <= rigth)
    {
        a[left] = b[i];
        left++;
        i++;
    }
    return count;
}

public static void main(String[] args)
{
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = scanner.nextInt();
    }
    int[] b = new int[n];
    System.out.println(getNumberOfInversions(a, b, 0, n - 1));
}
4

0 回答 0