提高算法的清晰度和效率

Question

在这段代码中，我试图在字符串列表中找到最常见的名称，以便程序在 O(nlogn) 中运行。我认识到这可以用字典在 O(n) 中完成。有什么明显的方法可以使这段代码更好吗？

def mostCommonName(L):

#in these two cases I'm making sure that if L has only one element in it

#or if it's empty that the correct result is returned before the loop

if len(L) == 1:

    return L[0]

if len(L) == 0:

    return None

#this automatically makes it nlogn

newL = sorted(L)

maxCount = 0

currCount = 1

maxName = set()

currName = newL[0]

for name in range(1,len(newL)):

    if newL[name] == currName:

        currCount += 1

    else:

        if currCount >= maxCount:

            maxCount = currCount

            currCount = 1

            maxName.add(currName)

            currName = newL[name]

        else:

            currCount = 1

            currName = newL[name]

if newL.count(newL[-1]) == maxCount:

    maxName.add(newL[-1])

if len(maxName) == 1:

    return maxName.pop()

return maxName

Answer 1

您可以改用groupby：from operator import itemgetterfrom itertools import groupbydef most_common_name(L):    l = sorted(L)    it = map(lambda pair: (pair[0], len(list(pair[1]))), groupby(l))    r, _ = max(it, key=itemgetter(1))    return rresult = most_common_name(['dan', 'david', 'dan', 'jen', 'james'])print(result)输出dan或者更易读的替代方案：from itertools import groupbydef len_group(pair):    return sum(1 for _ in pair[1])def most_common_name(l):    sorted_l = sorted(l)    r, _ = max(groupby(sorted_l), key=len_group)    return rresult = most_common_name(['dan', 'david', 'dan', 'jen', 'james'])print(result)在这两种选择中，想法是 groupby 处理连续值的分组。然后你可以找到最大的组并返回该组的键。这些解决方案是O(nlogn)，如果您对O(n)解决方案感兴趣，您可以使用 Counter 进行以下操作：from operator import itemgetterfrom collections import Counterdef most_common_name(l):    counts = Counter(l)    r, _ = max(counts.items(), key=itemgetter(1))    return rresult = most_common_name(['dan', 'david', 'dan', 'jen', 'james'])print(result)输出dan

Answer 2

稍微干净一点，同时保持相同的算法：def mostCommonName(L):    if len(L) == 0:        return None    newL = sorted(L)    occurrences, current_name = 1, newL[0]        best_occurrences, best_name = 1, newL[0]    for i in range(1, len(newL)):        if newL[i] == current_name:            occurrences += 1        else:            if occurrences > best_occurrences:                best_occurrences, best_name = occurrences, current_name            occurrences = 1            current_name = newL[i]    return best_name或者：from collections import Counterdef mostCommonName(L):    return Counter(L).most_common(1)[0][0]