如何优化统计列表支配元素的Python代码以提升运行速度？

问题定义 #

列表中的某个元素为支配元素（Dominator），当且仅当该元素右侧的所有元素（并非仅紧邻右侧的元素）都严格小于它。根据此定义，列表的最后一个元素自动成为支配元素。本函数需统计列表中支配元素的数量并返回该数值。例如，列表[42, 7, 12, 9, 13, 5]的支配元素为42、13和5。

现有代码及性能问题 #

我写出了可运行的代码，但运行速度较慢，请问该如何进行最优优化以提升运行速度？

现有代码：

def count_dominators(items):
    item_count = len(items)
    count = 0
    if item_count==0:
        return count;
        
    count+=1;
    
    if item_count==1:
        return count;
    
    for i in range(0,len(items)-1):
        flag=1
        for j in range(i+1,len(items)):
            
            if(items[j]>=items[i]):
                flag=0;
                break;
          
       
        if(flag==1):
            count+=1;
    return count

优化方案 #

你的代码采用两层嵌套循环，时间复杂度为O(n²)，当列表元素数量较大时，运行效率会显著下降。我们可以通过反向遍历的方式将时间复杂度降至O(n)，具体实现思路如下：

• 初始计数器设为1（因为最后一个元素必然是支配元素），同时记录当前遇到的最大值为列表最后一个元素的值。
• 从倒数第二个元素开始向前遍历每个元素：
  • 若当前元素大于记录的最大值，说明它是支配元素（右侧所有元素的最大值都小于它，自然所有元素都严格小于它），计数器加1，并更新最大值为当前元素的值。
  • 若当前元素小于等于最大值，直接跳过。

优化后的代码：

def count_dominators(items):
    if not items:
        return 0
    count = 1
    max_val = items[-1]
    # 从倒数第二个元素向前遍历
    for num in reversed(items[:-1]):
        if num > max_val:
            count += 1
            max_val = num
    return count

优化效果说明 #

• 时间复杂度从O(n²)降至O(n)，对于大规模数据（如包含10000个元素的列表），运行速度会有数量级的提升。
• 空间复杂度保持O(1)，无需额外开辟大量内存空间。

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