面试题51：数组中的逆序对

把逆序对拆成左右内部与跨段三类，递归排好两半后从后向前归并，并一次累计右段全部剩余元素。

学习目标

  • 能递归拆解逆序对为左右内部与跨段三类，归并时从后向前批量计数
  • 能解释"一次累计右段全部剩余元素"的计数方法
  • 能处理 与零长度输入边界

从“顺序”和“大小”同时满足开始

先预测：数组1、2、1、2、1中，相等的两个1不构成答案；逆序必须是前面元素严格大于后面元素。具体三对是下标1的2与下标2、4的1，以及下标3的2与下标4的1。

对数组A，定义为：

inv⁡(A)=∣{(i,j)∣0≤i<j<n, Ai>Aj}∣.\operatorname{inv}(A) = \left| \left\{ (i,j)\mid 0\le i<j<n,\ A_i>A_j \right\} \right|.

题目要求数组中的逆序对总数。两重循环可直接枚举所有下标对，时间O(n平方)；要优化，必须利用一次比较代表一整批比较结果。

拆成三类

把区间从中点分成左半L和右半R。任意逆序对只可能属于三类：两个下标都在L；两个都在R；前下标在L而后下标在R。前两类分别称为，第三类称为。

inv⁡(A)=inv⁡(L)+inv⁡(R)+cross⁡(L,R).\operatorname{inv}(A) = \operatorname{inv}(L) + \operatorname{inv}(R) + \operatorname{cross}(L,R).
总逆序数 = 左段内部 + 右段内部 + 跨段（归并时批量统计）147236左段（已有序）右段（已有序）跨段逆序：4>2、4>3（2 对） + 7>2、7>3、7>6（3 对） = 5 对左段内部 [1,4,7]：0 对 · 右段内部 [2,3,6]：0 对 · 跨段：5 对 → 总计 5归并时左指针值大于右指针值，则它与右段全部剩余元素都构成逆序，一次加完。分治递归处理左右段内部，跨段部分在归并中 O(n) 完成，总复杂度 O(n log n)。
总逆序数等于左段内部、右段内部与跨段三部分之和；分治递归处理前两部分。

递归先统计左右内部逆序，同时把两半各自排成升序。这样归并时不再逐个枚举跨段下标对，而能借助有序性批量计数。

分步1 / 3

分治拆三类

逆序对分三类：左内部、右内部、跨段。递归排序两半再归并。

总逆序数 = 左段内部 + 右段内部 + 跨段（归并时批量统计）147236左段（已有序）右段（已有序）跨段逆序：4>2、4>3（2 对） + 7>2、7>3、7>6（3 对） = 5 对左段内部 [1,4,7]：0 对 · 右段内部 [2,3,6]：0 对 · 跨段：5 对 → 总计 5归并时左指针值大于右指针值，则它与右段全部剩余元素都构成逆序，一次加完。分治递归处理左右段内部，跨段部分在归并中 O(n) 完成，总复杂度 O(n log n)。
总逆序数等于左段内部、右段内部与跨段三部分之和；分治递归处理前两部分。

为什么作者从后向前

设左半和右半都升序，i指向左半最大剩余元素，j指向右半最大剩余元素，indexCopy从输出区间尾部向前写。

若data[i]大于data[j]，那么右半从起点到j的所有剩余元素都不大于data[j]，因此也都严格小于data[i]。data[i]与这整段元素形成逆序对，可一次加入：

add⁡=j−(mid⁡+1)+1=j−start⁡−length⁡.\operatorname{add} = j-(\operatorname{mid}+1)+1 = j-\operatorname{start}-\operatorname{length}.

这就是原书的“一次累计一段逆序对”。随后把较大的data[i]写到输出尾部并左移i。

若data[i]小于或等于data[j]，无法据此断言data[i]大于右段其他元素；先把右侧更大元素写入输出尾部并左移j，不增加计数。相等时也走该分支，因为定义要求严格大于。

示例左段1、4、7，右段2、3、6。第一次比较7与6，7大于右段全部3个剩余值，一次加3；之后4大于3时再加2，总跨段数5。

批量计数为什么不重不漏

把左侧某元素写入输出时，它大于的右侧剩余元素全部仍未写入，这些配对第一次被统计；之后该左元素离开，不会再重复。

右侧已经写入输出的元素都大于或等于当前左元素，否则此前比较时就会由左元素胜出，所以它们不与当前左元素构成遗漏的逆序对。

这种借助有序连续区间、一次加上整段大小的动作称为。它把跨段统计与归并放在同一线性扫描中。

忠实还原作者入口与递归

入口复制一份数组，然后调用InversePairsCore。递归调用时故意交换data与copy参数；子层把有序结果写回本层将要读取的data，当前层再归并写入copy。

int InversePairsCore(
    int* data,
    int* copy,
    int start,
    int end);
 
int InversePairs(int* data, int length) {
    if (data == nullptr || length < 0) {
        return 0;
    }
 
    int* copy = new int[length];
    for (int i = 0; i < length; ++i) {
        copy[i] = data[i];
    }
 
    const int count =
        InversePairsCore(
            data, copy, 0, length - 1);
    delete[] copy;
    return count;
}
 
int InversePairsCore(
    int* data,
    int* copy,
    int start,
    int end) {
    if (start == end) {
        copy[start] = data[start];
        return 0;
    }
 
    const int length =
        (end - start) / 2;
    const int mid = start + length;
 
    const int left = InversePairsCore(
        copy, data, start, mid);
    const int right = InversePairsCore(
        copy, data, mid + 1, end);
 
    int i = mid;
    int j = end;
    int indexCopy = end;
    int count = 0;
 
    while (i >= start && j >= mid + 1) {
        if (data[i] > data[j]) {
            copy[indexCopy--] = data[i--];
            count += j - mid;
        } else {
            copy[indexCopy--] = data[j--];
        }
    }
 
    while (i >= start) {
        copy[indexCopy--] = data[i--];
    }
    while (j >= mid + 1) {
        copy[indexCopy--] = data[j--];
    }
    return left + right + count;
}

j减mid与源码的j减start再减length完全相同，因为mid等于start加length。保留源码表达式有助于逐行核对，使用mid则更直接显示“右段剩余数量”。

data与copy为何反复换角色

若每层递归都读data、写copy，子调用结束后还要把有序结果从copy复制回data，父层才能读取。作者改为调用InversePairsCore(copy, data, ...)，让读写角色在层级间交替。

调用层读取参数写入参数作用
顶层 [0..3]data Acopy B递归先把两半排入A，再从A归并到B
子层 [0..1]copy Bdata A参数互换，从B读取并写回A
基例 [0..0]data Acopy B复制单元素，建立子层读取源
子层 [2..3]copy Bdata A同样把右半排序写入A
顶层合并data Acopy BA含两个有序半段，B得到整段有序结果
递归调用交换data与copy角色，避免每层归并后再把整个区间复制回去。

这种省掉每层显式整段回拷，但阅读难度更高。关键不变式是：Core返回时，start到end的有序结果位于它的copy参数中。

入口最初把data复制到copy，保证无论递归层级从哪个缓冲区读取，叶子都有对应原值。顶层最终完整有序结果位于局部copy，函数只取计数后将它释放。

原输入并非保持不变

虽然顶层归并写入局部copy，但顶层两个子调用的copy参数是原始data；它们会把各自有序半段写回原数组。因此长度大于2时，调用后data通常变成“两个分别有序的半段”，而不是原顺序，也不一定是全局有序。

维度源码语义风险工程处理
相等元素不构成逆序对比较使用严格大于相等时取右段
nullptr, 0返回0作者Test8覆盖入口由空指针拦截
非空指针, 0未被length小于0拦截end变成-1应改为length小于等于0
输入数组递归子层写回data会被部分排序只读需求先复制工作数组
计数类型作者返回int降序大数组溢出使用int64_t
辅助空间长度n的copy加递归栈O(n)复用单缓冲区
作者示例在常规正长度输入上正确；零长度非空指针、输入改写与计数上界需要额外契约。

现代接口接收const视图并内部复制工作数组，可以明确保证调用者输入不变；作者裸指针接口没有这个契约。

零长度非空指针的递归漏洞

入口只拒绝length小于0，而不是小于或等于0。作者Test8传nullptr与0，被空指针条件拦截；但若传一个非空地址和length等于0，函数会分配零长度copy并调用Core的区间0到负1。

Core基例只判断start等于end，无法处理start大于end，随后继续构造非法区间并可能越界或无限递归。稳健入口应使用data为空或length小于等于0返回0，Core也可用start大于或等于end作为基例。

负length被源码拒绝。C++现代容器长度使用size_t，不存在负值，但要在从外部有符号协议转换前验证，避免负数变成巨大无符号值。

计数为什么必须使用64位

严格递减数组的每个下标对都是逆序对，长度n时达到最大值：

inv⁡max⁡(n)=n(n−1)2.\operatorname{inv}_{\max}(n) = \frac{n(n-1)}{2}.

作者返回int并用int保存left、right、count。32位有符号int下，n等于65537的最大逆序数已经超过上界，递归相加会溢出。旧页指出要用long long是正确工程建议，但需要明确作者源码本身仍是int。

归并排序递推为：

T(n)=2T(n/2)+O(n)=O(nlog⁡n),S(n)=O(n)+O(log⁡n).T(n)=2T(n/2)+O(n) =O(n\log n), \qquad S(n)=O(n)+O(\log n).

主辅助数组占O(n)，递归栈O(log n)，总额外空间仍为O(n)。

左右子区间的内部计数彼此独立，数据规模很大时可以并行递归；但父层必须等两半都排序完成后才能统计跨段逆序。最终结果仍按“左计数加右计数加跨段计数”归约。并行化不会改变比较规则，且每个任务写入的缓冲区区间必须互不重叠；否则为了提速引入的数据竞争会同时破坏排序结果与计数。

64位且不改输入的实现

下面用vector复制输入，用单个缓冲区做常见的从前向后归并。方向与作者不同但计数原理等价：当左当前值大于右当前值时，左段从i到mid都大于该右值，一次加mid减i加1。

#include <cstdint>
#include <span>
#include <vector>
 
std::int64_t mergeCount(
    std::vector<int>& values,
    std::vector<int>& buffer,
    std::size_t left,
    std::size_t right) {
    if (right - left <= 1) {
        return 0;
    }
    const std::size_t mid =
        left + (right - left) / 2;
    std::int64_t count =
        mergeCount(values, buffer, left, mid) +
        mergeCount(values, buffer, mid, right);
 
    std::size_t i = left;
    std::size_t j = mid;
    std::size_t out = left;
    while (i < mid && j < right) {
        if (values[i] <= values[j]) {
            buffer[out++] = values[i++];
        } else {
            count += static_cast<std::int64_t>(
                mid - i);
            buffer[out++] = values[j++];
        }
    }
    while (i < mid) {
        buffer[out++] = values[i++];
    }
    while (j < right) {
        buffer[out++] = values[j++];
    }
    for (std::size_t p = left;
         p < right;
         ++p) {
        values[p] = buffer[p];
    }
    return count;
}
 
std::int64_t inversePairs(
    std::span<const int> input) {
    std::vector<int> values(
        input.begin(), input.end());
    std::vector<int> buffer(values.size());
    return mergeCount(
        values, buffer, 0, values.size());
}

半开区间允许空输入自然满足right减left为0，无需构造end等于负1。计数转换在加法前完成，避免先以窄类型计算再赋给64位。

作者8组测试逐项还原

  1. 1、2、3、4、7、6、5期望3，三对都在尾部7、6、5中。
  2. 6、5、4、3、2、1期望15，覆盖长度6最大计数。
  3. 1、2、3、4、5、6期望0，覆盖完全有序。
  4. 单元素1期望0，直接递归基例。
  5. 两元素1、2期望0。
  6. 两元素2、1期望1。
  7. 1、2、1、2、1期望3，证明相等元素不计。
  8. nullptr、长度0期望0，由入口空指针分支返回。

作者测试会把输入数组交给函数，之后不再核对数组内容，因此没有发现输入被部分排序；也没有覆盖非空零长度或计数超过int。

#include <cassert>
#include <cstdint>
#include <vector>
 
void testInversePairs() {
    const std::vector<int> a{
        1, 2, 3, 4, 7, 6, 5};
    assert(inversePairs(a) == 3);
 
    const std::vector<int> descending{
        6, 5, 4, 3, 2, 1};
    assert(inversePairs(descending) == 15);
 
    const std::vector<int> ascending{
        1, 2, 3, 4, 5, 6};
    assert(inversePairs(ascending) == 0);
 
    const std::vector<int> equal{
        1, 2, 1, 2, 1};
    assert(inversePairs(equal) == 3);
    assert(inversePairs({}) == 0);
}

随机短数组可用双重循环参考实现对拍；同时保存输入副本，确认现代接口不修改调用者数据。大规模降序数组用于验证64位计数公式，不应再用O(n平方)参考实现。

本章练习

练习

问题 1： 逆序对的定义是什么？相等元素是否构成逆序？

问题 2： 归并时如何从后向前批量计数？

问题 3： 为什么计数必须用 64 位整数？

概念说明

本章核心概念包括：归并排序，一次累计一段逆序对。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 逆序对要求前下标更小且前值严格更大，相等不计。
  2. 总数分解为左右内部逆序与跨段逆序三部分。
  3. 归并排序让两个半段有序，从而一次累计一段逆序对。
  4. 作者从后向前合并；左最大值胜出时加右段全部剩余数。
  5. 递归交换data和copy角色，减少逐层回拷但会改写原输入。
  6. 非空指针配零长度未被源码入口正确拒绝，Core不支持空区间。
  7. 最大计数是n乘n减1再除2，大数组必须使用64位。
  8. 作者8组测试覆盖相等值与nullptr，但未覆盖输入保持和计数溢出。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

逆序对
数组中前面元素严格大于后面元素的一对下标。
分治
把问题拆成左右两半分别求解再合并。
归并
合并两个有序段的过程，本题从后向前合并并计数。
递归
函数调用自身，分治的典型实现方式。
批量计数
一次统计多个逆序对，从后向前归并时的计数技巧。
左段
归并时左半段已排序的子数组。
复习本章（5 题）

讨论

评论区加载中…