小学生都能看懂的题解 | #数组中的逆序对#

问题描述

想象你有一排数字卡片，比如 [1, 2, 3, 4, 5, 6, 7, 0]。我们要找出这样的情况：前面的数字比后面的数字大。这样的情况叫做“逆序对”。我们需要计算出有多少个这样的逆序对，并且最后的结果要除以 10000000071000000007 后取余数。

示例

• 输入：[1, 2, 3, 4, 5, 6, 7, 0]
• 输出：7
• 说明：逆序对包括：(1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0)。

解释

1. 分割数字卡片：
1. 我们可以把这排数字卡片分成两半。
2. 比如 [1, 2, 3, 4, 5, 6, 7, 0] 可以分成 [1, 2, 3, 4] 和 [5, 6, 7, 0]。
2. 递归处理每半边：
1. 我们继续把每半边再分成两半，直到每半边只剩下一个数字。
2. 例如，[1, 2, 3, 4] 可以进一步分成 [1, 2] 和 [3, 4]，然后再分成 [1] 和 [2]，以及 [3] 和 [4]。
3. 合并数字卡片并计算逆序对：
1. 当我们把数字卡片重新合并起来时，如果发现前面的数字比后面的数字大，就记下一个逆序对。
2. 例如，合并 [1, 2] 和 [3, 4] 时，没有逆序对；合并 [5, 6] 和 [7, 0] 时，发现 (5, 0), (6, 0), (7, 0) 是逆序对。
4. 重复步骤：
1. 重复以上步骤，直到我们处理完所有的数字卡片。
2. 例如，合并 [1, 2, 3, 4] 和 [5, 6, 7, 0] 时，发现 (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0) 是逆序对。
5. 最后计算结果：
1. 把所有逆序对的数量加起来，然后用这个总数除以 10000000071000000007 后取余数。

具体步骤

假设我们要找的数组是 [1, 2, 3, 4, 5, 6, 7, 0]：

1. 分割数字卡片：
1. 分成 [1, 2, 3, 4] 和 [5, 6, 7, 0]。
2. 递归处理每半边：
1. 再把 [1, 2, 3, 4] 分成 [1, 2] 和 [3, 4]。
2. 再把 [5, 6, 7, 0] 分成 [5, 6] 和 [7, 0]。
3. 再把 [1, 2] 分成 [1] 和 [2]。
4. 再把 [3, 4] 分成 [3] 和 [4]。
5. 再把 [5, 6] 分成 [5] 和 [6]。
6. 再把 [7, 0] 分成 [7] 和 [0]。
3. 合并数字卡片并计算逆序对：
1. 合并 [1] 和 [2]，没有逆序对。
2. 合并 [3] 和 [4]，没有逆序对。
3. 合并 [5] 和 [6]，没有逆序对。
4. 合并 [7] 和 [0]，发现 (7, 0) 是逆序对。
5. 合并 [1, 2] 和 [3, 4]，没有逆序对。
6. 合并 [5, 6] 和 [7, 0]，发现 (5, 0), (6, 0), (7, 0) 是逆序对。
7. 合并 [1, 2, 3, 4] 和 [5, 6, 7, 0]，发现 (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0) 是逆序对。
4. 最后计算结果：
1. 逆序对总数是 7，用 7 除以 1000000007 后取余数还是 7。

Java 实现

下面是具体的 Java 代码实现，并且详细解释每一步的操作：

public class InversionCount {

    private static final int MOD = 1000000007;

    // 计算逆序对数量
    public static int countInversions(int[] nums) {
        return countInversionsAndSort(nums, 0, nums.length - 1);
    }

    // 递归函数，计算逆序对数量并排序数组
    private static int countInversionsAndSort(int[] nums, int start, int end) {
        if (start >= end) {
            // 如果区间只有一个元素或为空，则返回0
            return 0;
        }

        int mid = start + (end - start) / 2;
        long inversions = 0L;

        // 递归计算左边的逆序对数量
        inversions += countInversionsAndSort(nums, start, mid);
        inversions = inversions % MOD;

        // 递归计算右边的逆序对数量
        inversions += countInversionsAndSort(nums, mid + 1, end);
        inversions = inversions % MOD;
        
        // 合并并计算跨两部分的逆序对数量
        inversions += mergeAndCount(nums, start, mid, end);
        inversions = inversions % MOD;

        return (int)inversions % MOD;
    }

    // 合并并计算跨两部分的逆序对数量
    private static int mergeAndCount(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        int count = 0;

        // 合并两个已排序的部分
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                // 如果左边的数小于等于右边的数，直接合并
                temp[k++] = nums[i++];
            } else {
                // 如果左边的数大于右边的数，记录逆序对
                temp[k++] = nums[j++];
                count += (mid - i + 1); // 计算跨两部分的逆序对数量
            }
        }

        // 复制剩余的元素
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        while (j <= end) {
            temp[k++] = nums[j++];
        }

        // 将合并后的有序数组复制回原数组
        for (i = start; i <= end; i++) {
            nums[i] = temp[i - start];
        }

        return count;
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        // 创建数组
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 0};

        // 调用countInversions方法
        int inversionCount = countInversions(nums);

        // 输出结果
        System.out.println("逆序对的数量是：" + inversionCount);
    }
}

解释

1. 分割数字卡片：
1. 使用递归方式将数组分成两半。
2. 递归处理每半边：
1. 递归地处理每半边，并计算每半边内的逆序对数量。
3. 合并数字卡片并计算逆序对：
1. 在合并过程中，如果发现前面的数字比后面的数字大，就增加逆序对的数量。使用临时数组 temp 来存储合并后的有序数组。
4. 重复步骤：
1. 重复以上步骤，直到处理完所有数字卡片。
5. 最后计算结果：
1. 把所有逆序对的数量加起来，然后用这个总数除以 10000000071000000007 后取余数。

代码解释

1. 主函数 main：
1. 初始化数组 nums。
2. 调用 countInversions 方法计算逆序对数量。
3. 输出结果。
2. 计算逆序对数量 countInversions：
1. 如果区间只有一个元素或为空，则返回 0。
2. 计算中点 mid，并递归计算左边和右边的逆序对数量。
3. 合并并计算跨两部分的逆序对数量。
3. 合并并计算跨两部分的逆序对数量 mergeAndCount：
1. 初始化临时数组 temp。
2. 使用双指针 i 和 j 分别指向左边和右边的起始位置。
3. 当 i 和 j 都在各自区间内时，比较两者的大小。
4. 如果左边的数小于等于右边的数，直接合并。
5. 如果左边的数大于右边的数，记录逆序对数量。
6. 复制剩余的元素。
7. 将合并后的有序数组复制回原数组。

这道题整体难度较大，如果能看懂文字解释的题解就算成功了😋，代码部分多看几次可以了。

如果这篇文字对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。