Skip to main content
 首页 » 编程设计

python之获取列表中小于特定元素的最小元素的最快方法

2025年05月04日13langtianya

我最好用一个例子来解释
假设,我有一个列表 [6,3,5,1,4,2]。

从索引 0 开始,找到所有小于(未标记)该索引处的值的项目。

Index 0: [6,3,5,1,4,2]   
Elements less than 6: 5{3,5,1,4,2}  
Visited array: [1 0 0 0 0 0] 
 
Index 1: [6,3,5,1,4,2]   
Elements less than 3: 2 {1,2} 
Visited array: [1 1 0 0 0 0] 
 
Index 2: [6,3,5,1,4,2]   
Elements less than 5: 3 {1,4,2} 
Visited array: [1 1 1 0 0 0] 
 
Index 3: [6,3,5,1,4,2]   
Elements less than 1: 0 {NULL} 
Visited array: [1 1 1 1 0 0] 
 
Index 4: [6,3,5,1,4,2]   
Elements less than 4: 1 {2} 
Visited array: [1 1 1 1 1 0] 
 
This yields an array as [5 2 3 0 1 0] 

目前正在使用,

def get_diff(lis): 
    ans=[] 
    for index,elem in enumerate(lis): 
        number_of_smaller=len(filter(lambda x:x<elem ,lis[index+1:])) 
        ans.append(number_of_smaller) 
    return ans 

但是,我感觉这样效率不高。我如何让它配得上一个巨大的 list ?我闻到前缀和了吗?谢谢,

请您参考如下方法:

您可以简单地在字典理解中使用列表理解来将项目保留为键,将小于它的项目保留为值(并使用 collections.OrderedDict 来保留顺序):

>>> from collections import OrderedDict 
>>> def get_diff(lis): 
...        return OrderedDict((item,[i for i in lis if i<item]) for item in lis) 

由于您的条件是 <没有必要排除项目本身,因为相比较而言,删除它的成本大于包含它。

此外,如果您想保留索引,您可以使用 enumerate遍历你的列表:

def get_diff(lis): 
       return OrderedDict((item,index),[i for i in lis if i<item]) for index,item in enumerate(lis)) 

如果您想计算这些项目的数量,您可以在 sum 中使用生成器表达式功能:

>>> from collections import OrderedDict 
>>> def get_diff(lis): 
...        return OrderedDict((item,sum(1 for i in lis if i<item)) for item in lis) 

注意:如果你想计数的项目少于之后的任何项目(具有更大的索引),你可以简单地在你的循环中使用索引:

>>> def get_diff(lis): 
...        return OrderedDict((item,sum(1 for i in lis[index:] if i<item)) for index,item in enumerate(lis)) 
...  
>>> get_diff(l).values() 
[5, 2, 3, 0, 1, 0]