获取最低计数*的列表中的元素

Question

我有一个列表,我想找到具有最低计数'*'的元素.

mylist = ['12*3','12345**6','11234']

所以这个小测试的答案是'11234'

这有效但很慢(我正在使用大量的基因组数据:

sorted(mylist, key = lambda x: x.count('*'))[0]

这不那么雄辩,但有效:

values = map(lambda x: x.count('*'), mylist)
print mylist[values.index(min(values))]

有没有更好的办法？我试图做一个schwartzian变换,但无法弄明白.

Answer 1

您可以使用min与key参数:

>>> mylist = ['12*3','12345**6','11234']
>>> min(mylist, key=lambda x: x.count('*'))
'11234'

key是一个函数,在iterable上的每个项目上调用,以与in中相同的方式指定顺序sorted.

上述方法将导致O(n)时间复杂度,其中排序为O(n log n).

更新:如果您的字符串非常长,那么您可以计算*循环中的出现次数,并在count与当前最小值相同时拒绝该字符串.如果找到出现0次的字符串,您也可以终止搜索:

def find(l):
    min_item = None
    min_val = float('inf')

    for x in l:
        current = 0
        for c in x:
            current += (c == '*')
            if current >= min_val:
                break
        else:
            # Found new minimum, update
            min_item = x
            min_val = current

        # Can't get lower than 0
        if min_val == 0:
            break

    return min_item

print(find(['12*3','11234', '12345**6', '1'])) # '11234'