重要逆序对

周子力大约 6 分钟教学文档算法设计与分析分治法递归归并计数中高难度Python

重要逆序对

题目描述

给定整数数组 nums，统计满足以下条件的下标对 $(i,j)$ 的个数：

i<j,\qquad nums[i]>2\cdot nums[j].

下标从0开始。允许负数、0和重复值；数组为空或只有一个元素时计数为0。要求不修改输入，并同时返回一个非递减的新数组，结果格式为 (有序数组, 重要逆序对数量)。

示例： [2, 4, 3, 5, 1] 中有3对，原始下标分别为 $(1,4)$ 、 $(2,4)$ 、 $(3,4)$ ；返回 ([1, 2, 3, 4, 5], 3)。

本题与逆序对共用“按原始位置分治、排序并计数”的结构，但判断条件不同。普通逆序对要求 $nums[i]>nums[j]$ ，不能将原来的归并计数规则直接照搬。尤其在负数输入中，两种关系并不互相包含。

题目分析

仍然分为三类位置对

按原始下标把数组分成左右两段，一对位置只能属于：左段内部、右段内部、跨越左右两段。两侧内部数量由递归求出，当前层负责统计跨段数量并合并排序。

定义 solve(lo, hi)：返回原始位置区间 $[lo,hi)$ 的有序列表及重要逆序对数。长度不超过1时，返回区间副本和0。总计数满足：

C=C_{left}+C_{right}+C_{cross}.

左右段内部虽然已排序，但左右段的归属仍来自原始下标划分。因此左段的任意原始位置都先于右段的任意原始位置，跨段统计自动满足 $i<j$ 。

在合并前单独统计跨段配对

设左右有序结果为 left、right。固定左侧元素 x，右侧满足 x > 2 * right[j] 的元素一定组成一个前缀：因为乘以正数2保持顺序。

按非递减顺序遍历 left，维护右侧前缀长度 j。当左值增大时，已有合格右值不会失效，j 只向右移动。对每个左值，将此时的 j 加入跨段数量。

这一步只做计数，然后再按普通大小关系合并两个有序列表。统计条件是 x > 2*y，排序条件是 x <= y，两者必须分开。

正确性依据

每个左值对应的右侧前缀恰好包含全部合格右值，所以跨段统计没有漏计或重复。三个位置类别互斥且完整，左右内部计数又由递归正确返回，故三者之和就是当前区间的答案。合并同时保留所有元素，为父调用提供有序列表。

实现代码

Python 归并与双指针计数实现

def count_important_pairs(nums):
    """返回(有序新列表, 重要逆序对数量)，不修改输入。"""
    def solve(lo, hi):
        if hi - lo <= 1:
            return nums[lo:hi], 0
        mid = (lo + hi) // 2
        left, left_count = solve(lo, mid)
        right, right_count = solve(mid, hi)

        cross_count = 0
        j = 0
        for x in left:
            while j < len(right) and x > 2 * right[j]:
                j += 1
            cross_count += j

        merged = []
        i = j = 0  # 排序重新使用指针，不沿用计数阶段的j
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, left_count + right_count + cross_count

    return solve(0, len(nums))


for nums in [[2, 4, 3, 5, 1], [1, 3, 2, 3, 1], [-3, -2], [-1, -1], []]:
    print(count_important_pairs(nums))

输出：

([1, 2, 3, 4, 5], 3)
([1, 1, 2, 3, 3], 2)
([-3, -2], 1)
([-1, -1], 1)
([], 0)

Python 整数能精确表示 2 * right[j] 和计数。若迁移到固定宽度整数语言，应保证加倍运算和累计计数不会溢出。

算法执行过程

主示例先分成 [2,4] 和 [3,5,1]。

阶段	有序子结果与内部计数	当前层跨段统计
处理 `[2,4]`	`[2,4]`，0对	$2>2\times4$ 不成立
处理 `[5,1]`	`[1,5]`，1对	$5>2\times1$ 成立
合并 `[3]` 与 `[1,5]`	`[1,3,5]`，内部合计2对	3只与右侧1形成1对
根处理左值2	左结果 `[2,4]`；右结果 `[1,3,5]`	$2>2\times1$ 不成立，`j=0`，加0
根处理左值4	同上	1合格，3不合格，`j=1`，加1
根合并返回	`[1,2,3,4,5]`	总数 $0+2+1=3$

根的跨段配对是原数组中的4与最后的1。原始数组开头的2与最后的1满足相等 $2=2\times1$ ，因题目要求严格大于，不计入答案。

负数例子 [-3,-2] 没有普通逆序对，却有重要逆序对，因为 $-3>2\times(-2)=-4$ 。两个相等的负数 [-1,-1] 也会构成重要逆序对，不能套用普通逆序对中“相等不计数”的结论。

复杂度分析

按整数比较、加倍和加法为单位成本，令数组长度为 $n$ 。

时间复杂度： $n\geq2$ 时为 $O(n\log n)$ 。每层的跨段统计中，左指针和右指针各只向前移动；之后的排序合并也只线性处理元素。于是有 $T(n)=2T(n/2)+O(n)$ ，奇数长度时两侧规模相差1。空数组或单元素为 $O(1)$ 。

辅助空间复杂度： $O(n+1)$ ，来自递归中的有序列表、合并切片和调用栈；栈深度为 $O(\log(n+1))$ 。最终有序输出另占 $O(n)$ ，计数占一个整数。若考虑整数实际位数，算术成本和计数的存储还与位数有关。

计数最多为 $n(n-1)/2$ ，例如所有元素都为 $-1$ 时，每个 $i<j$ 都满足 $-1>-2$ 。

易错点

在右值比左值小时直接加左侧剩余长度。 那是普通逆序对的规则，本题必须检查加倍后的右值。
将指针 j 在每个左值处重置为0。 仍可正确统计，但最坏会退化为当前层的二次扫描；有序性允许保留它。
将计数阶段的指针带入排序。 排序要重新从两侧起点开始，否则漏掉元素。
只处理正数或认为相等值永远不计。 题设允许负数，相等负数可能满足条件。
把严格大于改成大于等于。 [2,1] 不构成重要逆序对。
先对原数组整体排序再统计。 会丢失原始先后关系，必须按原始位置分治。

课堂练习

[2, 1] 和 [3, 1] 的重要逆序对数分别是多少？
[-2, -2, -2] 中有多少普通逆序对、多少重要逆序对？
[5, 2, 1] 中哪些原始下标对符合条件？
当前层左结果为 [2,4,9]、右结果为 [1,3]，各左值对应的前缀长度是多少？跨段共有多少对？

参考答案

分别为0和1，因为 $2=2\times1$ 而 $3>2\times1$ 。
普通逆序对为0；重要逆序对为3，三个 $i<j$ 均满足 $-2>-4$ 。
$(0,1)$ 和 $(0,2)$ ，共2对。 $(1,2)$ 满足 $2=2\times1$ ，不计。
前缀长度依次为0、1、2，跨段数量为 $0+1+2=3$ 。