如何用O(n)时间复杂度求解列表各元素的superior数量

核心问题性质 #

该问题属于经典逆序对变种，目标是统计每个元素右侧所有严格大于它的元素总数。

解法1：固定小数值范围场景下的严格O(n)实现 #

当题目约定输入数值的范围为固定有限大小（例如所有元素取值在0~1000之间）时，可通过倒序遍历+桶计数实现严格O(n)时间复杂度：

• 实现思路：
  • 首先取数组最大值初始化计数桶数组，记录已遍历元素的出现次数
  • 从右往左遍历原数组，已遍历的所有元素都是当前元素右侧的元素，直接对大于当前数值的桶计数求和，就是当前元素的superior总数
  • 求和操作因为数值范围固定，时间开销为常数，不影响复杂度阶
• 注意：如果数值范围无限制，该方法空间开销不可控，推荐使用解法2。

解法2：通用场景下的O(n log k)实现（k为去重后数值个数，面试中通常被认可为最优解） #

如果输入存在大整数、负数等大范围数值，可通过**离散化+树状数组（Fenwick Tree）**实现，时间复杂度接近线性：

• 实现步骤：
  1. 离散化处理：将原数组所有元素去重后排序，给每个数值映射到连续的排名，压缩数值范围
  2. 初始化树状数组，用于维护已遍历元素的计数前缀和
  3. 倒序遍历原数组：
     • 对当前元素，查询树状数组中小于等于当前值的元素总个数，用已遍历的元素总数减去该值，就是当前元素右侧严格大于它的元素个数
     • 将当前元素的排名更新到树状数组中
  4. 遍历完成后直接返回结果数组即可
• 示例验证：

输入[1, 3, 5, 2, 3, 6]，倒序遍历顺序为6→3→2→5→3→1

• 遍历6：已遍历总数为0，对应结果为0，插入6，已遍历数更新为1
• 遍历3：已遍历总数为1，小于等于3的元素个数为0，对应结果为1-0=1，插入3，已遍历数更新为2
• 遍历2：已遍历总数为2，小于等于2的元素个数为0，对应结果为2-0=2，插入2，已遍历数更新为3
• 遍历5：已遍历总数为3，小于等于5的元素个数为2（2、3），对应结果为3-2=1，插入5，已遍历数更新为4
• 遍历3：已遍历总数为4，小于等于3的元素个数为2（2、3），对应结果为4-2=2，插入3，已遍历数更新为5
• 遍历1：已遍历总数为5，小于等于1的元素个数为0，对应结果为5-0=5，插入1
  最终输出为[5, 2, 1, 2, 1, 0]，和示例完全匹配。

• 参考Python实现：

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 1)
    
    # 单点更新：排名idx位置计数加delta
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    # 前缀和查询：查询排名1到idx的总计数
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def count_superior(nums):
    # 离散化映射排名
    sorted_unique = sorted(set(nums))
    rank_map = {val: i+1 for i, val in enumerate(sorted_unique)} # 排名从1开始适配树状数组
    max_rank = len(sorted_unique)
    ft = FenwickTree(max_rank)
    res = [0] * len(nums)
    traversed_count = 0
    # 倒序遍历
    for i in range(len(nums)-1, -1, -1):
        cur_num = nums[i]
        cur_rank = rank_map[cur_num]
        # 右侧严格大于的个数 = 已遍历总数 - 小于等于当前数的个数
        res[i] = traversed_count - ft.query(cur_rank)
        ft.update(cur_rank, 1)
        traversed_count += 1
    return res

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