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

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

题目描述

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

考察公司：小米

考察时间：2025.05.26

image-20241107211724343

题意分析

给定整数数组，统计逆序对总数：即满足 i < j 且 nums[i] > nums[j] 的下标对 (i, j) 的个数。注意比较的是「严格大于」，相等元素不构成逆序对。

数据规模是关键信号：数组长度可达 $5 \times 10^4$，暴力双重循环要做约 $1.25 \times 10^9$ 次比较，必然超时，必须找到低于平方级的做法。

边界上注意：空数组或单元素数组没有任何数对，直接返回 0；逆序对总数最多约 $1.25 \times 10^9$，本题规模下未超出 int 范围，若规模再大需换 long。

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

核心思路

问题关键：暴力枚举每一对下标需要 $O(n^2)$。要降低复杂度，必须利用区间有序后可以批量计数这一性质。

为什么选归并排序：递归先统计左右区间内部的逆序对；合并两个有序区间时，若 nums[i] > nums[j]，左区间剩余的 nums[i..mid] 都大于 nums[j]，可一次增加 mid - i + 1。这样计数完全融入线性合并过程。

不变量与正确性：合并过程中，临时数组始终有序，左右指针之前的元素都已处理。每个逆序对会在两个下标第一次被分到不同区间的那一层，随右侧较小元素被取出时统计一次，因此不重不漏。合并结果写回后区间重新有序，供上一层继续使用。

解题步骤

  1. 在入口创建一个与原数组等长的临时数组，所有递归层共用。
  2. 将区间 [left, right] 分成两半，递归得到左右区间的逆序对数量。
  3. 合并时维护左右指针：左值不大于右值就取左值；否则取右值，并把左侧剩余元素个数加入答案。
  4. 搬完剩余元素，把临时数组的当前区间写回原数组。

例如合并 [5,7] 和 [4,6]：取 4 时增加 2，取 6 时再增加 1，当前层得到 3 个跨区间逆序对。

代码实现

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
}

复杂度分析

  • 时间复杂度：$O(n \log n)$。递归深度为 $O(\log n)$，每层合并总共处理 $n$ 个元素。
  • 空间复杂度：$O(n)$。临时数组占 $O(n)$，递归栈占 $O(\log n)$。

关键点总结

  • 答案由「左区间内部 + 右区间内部 + 跨区间」三部分组成。
  • nums[i] > nums[j] 时才能批量增加 mid - i + 1；相等不算逆序对。
  • 每次合并后必须写回有序结果，这是上一层正确计数的前提。
  • 若追问替代方案，可回答「离散化 + 树状数组」，复杂度同为 $O(n \log n)$，但归并实现更直接。

易错点总结

  • 合并条件写成 <：[1,1] 会把相等元素误计为 1 对；应使用 <= 先取左值。
  • 增量写成 mid - i：[2,1] 会漏掉当前的 nums[i]，正确数量是 mid - i + 1。
  • 忘记累加左右递归结果：[7,5,6,4] 只会得到顶层的 3 对，而不是总数 5。
  • 忘记把合并结果写回：上一层读到的区间仍无序，批量计数的前提被破坏。

相似题目

题目 难度 考察点
315. 计算右侧小于当前元素的个数 困难 计数落到每个下标而非总和，归并时需携带原始下标
327. 区间和的个数 困难 先转前缀和数组，再在归并中统计落入 [lower, upper] 的差值对
493. 翻转对 困难 条件变为 nums[i] > 2 * nums[j]，统计与合并需用两套独立指针
补充题 8. 计算数组的小和 中等 结算的量从「逆序对个数」换成「元素值之和」，框架完全复用
面试题-最小交换次数（任意交换与相邻交换） 困难 相邻交换的最少次数恰等于逆序对总数，归并计数即最终答案