LeetCode 补充题 218. 数组中的逆序对计数

2026-09-14 HGNULB 约 5 分钟

文章信息 2 个分类 7 个标签

分类

补充题困难

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ LCR 170. 交易逆序对的总数

LeetCode 原题返回逆序对总数；本文将数组长度上限扩展到 100000，结果对 1000000007 取模。

:::

给定整数数组 nums，返回逆序对数量对 1000000007 取模的结果。

逆序对满足 i < j 且 nums[i] > nums[j]。

示例 1：

输入： nums = [3,2,1]
输出： 3

提示：

0 <= nums.length <= 100000
允许原地排序数组。

题意分析

逆序对按两项的位置分成左半区内部、右半区内部、跨越两半区三类。前两类递归解决，跨区间部分借助归并时的有序性批量计数，从而避免逐对比较。

解法：归并排序计数

核心思路

[!blue]

归并前，左右半区已经各自有序。若左值不大于右值，先取左值，不产生跨区间逆序对；否则右值小于左侧从 i 到 mid 的所有剩余元素，一次增加 mid-i+1 对。

左右子区间内部的逆序对已经递归算完，这里只补跨区间部分，不会重复计数。归并结果写回后，上一层才能继续利用有序性批量计数。

计数过程保留 64 位真实数量，最外层再取模。面试先说明“为什么一次能加整段长度”，再说明大计数的表示，避免只背归并模板。

解题步骤

区间长度不超过 1 时返回 0，否则递归处理左右两半并累加内部逆序对。

合并两段有序区间，左值不大于右值时先取左值。

右值更小时，增加左半区尚未取出的元素数，再取右值。

补齐剩余元素并将归并结果写回原数组，最外层将总数取模后返回。

代码实现

class Solution {
    public int reversePairs(int[] nums) {
        int[] temp = new int[nums.length];

        return (int) (mergeSort(nums, temp, 0, nums.length - 1) % 1000000007);
    }

    private long mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        long count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);
        int i = left;
        int j = mid + 1;
        int idx = left;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[idx++] = nums[i++];
            } else {
                count += mid - i + 1;
                temp[idx++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[idx++] = nums[i++];
        }

        while (j <= right) {
            temp[idx++] = nums[j++];
        }

        for (int k = left; k <= right; k++) {
            nums[k] = temp[k];
        }

        return count;
    }
}

func reversePairs(nums []int) int {
    temp := make([]int, len(nums))
    return int(mergeSortPairs(nums, temp, 0, len(nums)-1) % 1000000007)
}

func mergeSortPairs(nums []int, temp []int, left int, right int) int64 {
    if left >= right {
        return 0
    }
    mid := left + (right-left)/2
    count := mergeSortPairs(nums, temp, left, mid) + mergeSortPairs(nums, temp, mid+1, right)
    i := left
    j := mid + 1
    idx := left
    for i <= mid && j <= right {
        if nums[i] <= nums[j] {
            temp[idx] = nums[i]
            i++
        } else {
            count += int64(mid - i + 1)
            temp[idx] = nums[j]
            j++
        }
        idx++
    }
    for i <= mid {
        temp[idx] = nums[i]
        i++
        idx++
    }
    for j <= right {
        temp[idx] = nums[j]
        j++
        idx++
    }
    for k := left; k <= right; k++ {
        nums[k] = temp[k]
    }
    return count
}

复杂度分析

时间复杂度：$O(n\log n)$。

空间复杂度：额外空间 $O(n)$。

关键点总结

[!green]

归并时若右侧元素更小，左半段尚未取出的元素都与它构成逆序对；全部计数用 64 位，最外层再取模。

易错点总结

[!yellow]

相等元素不构成逆序对，比较时用左值不大于右值的分支先取左值。

增量是 mid-i+1，只统计尚未合并的左侧元素。

n=100000 时最大计数超过 32 位有符号整数，累加全过程使用 64 位。

每层必须写回有序结果，上一层的批量计数才成立；本题允许修改输入数组。

相似题目

题目	难度	关联与区别
剑指 Offer 51. 数组中的逆序对	困难	归并时累计跨区逆序对的过程相同；该题返回精确总数，本题扩大数组长度上限并对 1000000007 取模，计数需使用 64 位整数。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/796743072138

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！