AcWing算法基础课-788逆序对的数量-Java题解

在处理排序相关的问题时，逆序对的数量是一个常见而重要的概念。在AcWing的算法基础课程中，题目“788逆序对的数量”要求我们计算给定数组中的逆序对数量。逆序对是指对 (i, j) 满足 i < j 且 arr[i] > arr[j] 的数组元素对。接下来，我们将讨论如何有效地计算逆序对的数量，并提供相应的Java代码示例。

逆序对的概念

逆序对是数组中一对元素的关系，具体来说，在数组中，如果前面的元素大于后面的元素，则形成一个逆序对。例如，在数组 [3, 2, 5, 1] 中，逆序对有 (3, 2)、(3, 1)、(2, 1)，总共有3个逆序对。

逆序对的暴力解法

最简单的解决办法是使用双重循环，遍历所有可能的元素对，然后统计满足条件的逆序对。算法的时间复杂度是 O(n^2)，这在大多数情况下并不高效，特别是当数组长度较大时。

以下是暴力解法的Java代码示例：

public class InversionCount {
    public static int countInversions(int[] arr) {
        int count = 0;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 1};
        System.out.println("逆序对的数量: " + countInversions(arr));
    }
}

归并排序法计算逆序对

可以通过归并排序的过程来有效地计算逆序对，这样可以将时间复杂度降低到 O(n log n)。在归并排序合并两个已经排好序的子数组时，当我们将一个子数组的元素与另一个子数组的元素进行比较时，可以判断形成的逆序对的数量。

具体来说，如果当前的左子数组中的元素大于右子数组中的元素，那么当前左子数组及其后所有元素都与当前右子数组中的元素形成逆序对。通过这种方式，我们可以计算出逆序对的数量。

以下是使用归并排序法来计算逆序对的Java代码示例：

public class InversionCount {
    private static int mergeAndCount(int[] arr, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        System.arraycopy(arr, left, leftArr, 0, leftArr.length);
        System.arraycopy(arr, mid + 1, rightArr, 0, rightArr.length);

        int i = 0, j = 0, count = 0;
        int k = left;

        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
                count += (leftArr.length - i);
            }
        }

        while (i < leftArr.length) {
            arr[k++] = leftArr[i++];
        }

        while (j < rightArr.length) {
            arr[k++] = rightArr[j++];
        }

        return count;
    }

    private static int mergeSortAndCount(int[] arr, int left, int right) {
        int count = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            count += mergeSortAndCount(arr, left, mid);
            count += mergeSortAndCount(arr, mid + 1, right);
            count += mergeAndCount(arr, left, mid, right);
        }
        return count;
    }

    public static int countInversions(int[] arr) {
        return mergeSortAndCount(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 1};
        System.out.println("逆序对的数量: " + countInversions(arr));
    }
}

总结

通过使用归并排序法，我们有效地从 O(n^2) 降低了计算逆序对的时间复杂度到 O(n log n)，这对于大规模数据处理非常重要。掌握这种算法不仅有助于解决逆序对的问题，也提高了我们在排序和分治算法方面的理解与应用能力。这对于后续的算法学习和比赛都是非常有益的。希望这个解法能够帮助你更加深入地理解逆序对的计算。