Python 函数以最小可能的时间顺序 (O(n)) 在字典中查找所有第二低的 SCORERS

Question

你好，我想写一个 python 函数来查找字典中所有得分最低的人，时间复杂度为 o(n)。

该函数应处理任何字典索引中的第二小值，包括前 k,v 对。

函数也应该处理重复的最低分数。

测试用例：

second_lowest_scorers({"hri":6.2,"dav":1.1,"asv":1.1,"wrs":12.3,"dup":6.2,"awe":43.2,"asw":22.2,"asd":6.2})

预期输出：

['asd', 'dup', 'hri'] (optional: sorted by name)

解释 asv 和 dav 得分为 1.1，这是最低分。 asd、dup、hri 得分次低。

到目前为止，我已经使用多个循环解决了它。

def lowest_scores(names_scores):

    lowest_score=min(names_scores.values())
    
    lowscorers=[]

    low_scorer_dict = { k : v for k,v in names_scores.items() if v != lowest_score}
    
    second_lowest_score = min(low_scorer_dict.values())

    for k,v in low_scorer_dict.items():
        if v == second_lowest_score:
            lowscorers.append(k)
        
    return sorted(lowscorers)

不想使用外部函数来解决算法问题

Answer 1

O(N) 解

data = {"hri":6.2,"dav":1.1,"asv":1.1,"wrs":12.3,"dup":6.2,"awe":43.2,"asw":22.2,"asd":6.2}

vals = set(data.values()) # create set so we don't get duplicates
vals.remove(min(vals)) # remove the most minimum
minVal = min(vals) # this is the second minimum

for k,v in data.items():
    if v == minVal :
        print(k) # where value is second minimum

hri
dup
asd

Python 函数以最小可能的时间顺序 (O(n)) 在字典中查找所有第二低的 SCORERS

Python function to find ALL second lowest SCORERS in a Dictionary with minimal possible order of time (O(n))

python

algorithm

big-o

python-3.x