在列表中獲取少於特定元素的最小元素的最快方法

Question

我最好用示例來解釋
假設我有一個列表[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 

不過，我有一種感覺，這不會是有效的。我如何使它值得一個巨大的名單？我能聞到前綴總和嗎？謝謝，

Answer 1

您可以簡單地用一個列表理解的字典修真內保留項目爲重點，哪些是低於它的價值的物品（和使用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] 

Answer 2

my_list = [6,3,5,1,4,2] 

def get_diff(lis): 
    result = [] 
    for visited, i in enumerate(range(len(lis))): 
     limit = lis[i] 
     elem = filter(None, [x if x < limit else None for x in lis][visited + 1:]) 
     result.append(len(elem)) 
    return result 

print get_diff(my_list) 
#[5, 2, 3, 0, 1, 0]