统计列表满足i<j且list[i]>list[j]的逆序对 求低时间复杂度解法

你要统计的i<j且list[i]>list[j]的数对就是经典的逆序对，暴力O(n²)解法仅适合极小规模数据，最优的通用实现时间复杂度为O(nlogn)，有两种主流实现思路： #

方法1：基于归并排序的实现 #

核心思路 #

利用归并排序分治的特性：

• 把数组递归拆成左右两个子数组，分别统计左右子数组内部的逆序对
• 合并左右有序子数组时，统计跨左右子数组的逆序对：如果右子数组当前元素小于左子数组当前元素，那么左子数组剩余所有元素都和该右元素构成逆序对，直接累加对应数量即可

实现代码 #

def count_inversions(arr):
    # 辅助归并函数
    def merge(left, right):
        merged = []
        i = j = inv_count = 0
        # 合并时统计跨区间逆序对
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                # 左数组剩余len(left)-i个元素都比right[j]大，全部构成逆序对
                inv_count += len(left) - i
                j += 1
        # 拼接剩余元素
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, inv_count
    
    # 分治递归函数
    def merge_sort(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, inv_left = merge_sort(arr[:mid])
        right, inv_right = merge_sort(arr[mid:])
        merged, inv_cross = merge(left, right)
        # 总逆序对 = 左内部 + 右内部 + 跨左右
        return merged, inv_left + inv_right + inv_cross
    
    _, total = merge_sort(arr)
    return total

# 测试样例
print(count_inversions([5,2,10,9,7])) # 输出4，符合预期

方法2：基于树状数组（Fenwick Tree）的实现 #

核心思路 #

• 先对数组做离散化处理（兼容数值过大的场景）
• 从数组末尾倒序遍历，每遍历一个元素，查询树状数组中已插入的、比当前元素小的元素数量（就是当前元素能构成的逆序对数量），累加到总计数里，再把当前元素插入树状数组

实现代码 #

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0]*(self.n + 1)
    
    def update(self, idx, delta=1):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def count_inversions_fenwick(arr):
    # 离散化处理，把数值映射到1~rank的连续区间
    sorted_unique = sorted(set(arr))
    rank = {v:i+1 for i, v in enumerate(sorted_unique)}
    max_rank = len(sorted_unique)
    ft = FenwickTree(max_rank)
    total = 0
    # 倒序遍历
    for num in reversed(arr):
        r = rank[num]
        # 查询比当前数小的已插入元素数量
        total += ft.query(r-1)
        ft.update(r)
    return total

# 测试样例
print(count_inversions_fenwick([5,2,10,9,7])) # 输出4，符合预期

两种方案对比 #

• 归并排序实现无需额外处理数值范围，代码逻辑更直观，适合绝大多数场景
• 树状数组实现常数项更低，运行速度更快，适合数值范围可控或者需要更高性能的场景

内容的提问来源于stack exchange，提问作者om1999