LeetCode 剑指 Offer 51. 数组中的逆序对

约 6 分钟
文章信息 20 个分类 7 个标签
分类
LeetCode CodeTop 困难 已解决 未掌握 历史考题 50-100 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 华为 微软 美团 京东 小米 百度 快手 虾皮 金山
标签
数组 二分查找 分治 有序集合 线段树 归并排序 树状数组

题目描述

✅ 剑指 Offer 51. 数组中的逆序对

image-20261001230752576

:::fold 历史考题

考察公司：小米
考察时间：2025.05.26

:::

题意分析

逆序对是两个原始下标满足 i < j，且值满足 nums[i] > nums[j] 的元素对。需要统计所有这样的下标对，不要求两个元素相邻，相等的值也不构成逆序对。

不同下标上的元素分别计数，即使数值相同，它们与其他元素形成的逆序对也属于不同的下标对。直接枚举所有下标对需要平方级时间，可以在排序过程中批量计数；下面的实现会同时将输入数组排成升序。

解法：归并排序统计跨区间逆序对

核心思路

[!blue]

把原数组区间分成左右两半，逆序对恰好分为三类：两个元素都在左半、都在右半，或者左半元素与右半元素各一个。前两类可以递归求解，当前层只负责第三类，最后把三部分相加。

让递归函数同时完成两件事：返回当前区间的逆序对数，并把该区间排好序。这样合并左右两半时，只需比较各自尚未处理的最小值，就能批量判断跨区间逆序对。左右半区来自原始下标连续的两段，即使内部已经排序，左半的每个元素在原数组中仍都位于右半元素之前。

设左指针为 i，右指针为 j，左半结束位置为 mid：

  • 若 nums[i] <= nums[j]，右半剩余元素都不小于 nums[j]，因此 nums[i] 不会再与它们形成逆序对，可以先放入左值。
  • 若 nums[i] > nums[j]，左半已经有序，nums[i..mid] 全都大于 nums[j]。它们都能和这个右值构成逆序对，一次增加 mid - i + 1，再放入右值并移动 j。

每次批量计数只针对一个刚要取走的右值，所配对的左值正是尚未取走且更大的那些，不会在当前合并中重复计数。任意一对原始下标也只会在递归划分中第一次分属左右两半的那一层统计，所以不会跨层重复或遗漏。

合并结束后，把辅助数组中当前区间的有序结果写回原数组，让上一层继续使用同样的有序性。空区间或单元素区间没有逆序对，返回 0 即可。

解题步骤

  1. 创建与原数组等长的辅助数组 temp，从整个区间开始递归。
  2. 区间长度不超过一时返回 0；否则分成 [left, mid] 和 [mid + 1, right]。
  3. 递归处理左右区间，把它们各自的逆序对数相加作为当前 count。
  4. 合并两个有序区间：左值不大于右值时取左值；否则取右值，并增加 mid - i + 1 对。
  5. 搬完未耗尽一侧的元素，将合并结果写回 nums[left..right]，返回 count。

代码实现

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

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

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

        int mid = left + (right - left) / 2;
        int 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 {
                // 左半区剩余元素都大于 nums[j]，一次性计数。
                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 mergeSortPairs(nums, temp, 0, len(nums)-1)
}

func mergeSortPairs(nums []int, temp []int, left int, right int) int {
    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 {
            // nums[i..mid] 都能和 nums[j] 构成逆序对。
            count += 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
}

复杂度分析

设数组长度为 $n$。

  • 时间复杂度：$O(n\log n)$。递归有 $O(\log n)$ 层，每层合并与写回的总元素数为 $n$，计数随合并完成。
  • 辅助空间复杂度：$O(n)$。共享辅助数组占 $O(n)$，递归栈占 $O(\log n)$。空数组直接结束，不会访问元素。

关键点总结

[!green]

  • 递归既统计区间内部的逆序对，也为上层提供有序区间。
  • 取走较小的右值时，左半剩余元素能够整段与它配对。
  • 左右内部与跨区间三类互不重叠，相等元素不计入逆序对。

易错点总结

[!yellow]

  • 比较条件写成 < 而不是 <=，会让相等元素进入计数分支，误认为它们构成逆序对。
  • 增量是 mid - i + 1，必须包含当前的 nums[i]；漏掉 + 1 会少计。
  • 当前层需要保留左右递归返回的数量，不能只返回本次合并统计的跨区间数量。
  • 不能在排序全部结束后再统计，此时原有次序已经改变；应在归并对应的原始左右分组时计数。
  • 忘记把合并结果写回原数组，会让上一层在无序数据上批量判断，破坏计数前提。

相似题目

题目 难度 关联与区别
315. 计算右侧小于当前元素的个数 困难 每个元素右侧较小值数量累加就是逆序对总数，归并或树状数组的计数思路可复用。
493. 翻转对 困难 原题条件为左值大于右值两倍，本题是普通严格大于，不能沿用同一个比较条件。
补充题 218. 数组中的逆序对计数 困难 都在归并排序时统计跨半区的逆序对；补充题要求对结果取模。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/57449742
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！