提高算法的清晰度和效率

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 loopif len(L) == 1:    return L[0]if len(L) == 0:    return None#this automatically makes it nlognnewL = sorted(L)maxCount = 0currCount = 1maxName = 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 itemgetter

from itertools import groupby

def 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 r

result = most_common_name(['dan', 'david', 'dan', 'jen', 'james'])

print(result)

输出

dan

或者更易读的替代方案：

from itertools import groupby

def 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 r

result = most_common_name(['dan', 'david', 'dan', 'jen', 'james'])

print(result)

在这两种选择中，想法是 groupby 处理连续值的分组。然后你可以找到最大的组并返回该组的键。这些解决方案是O(nlogn)，如果您对O(n)解决方案感兴趣，您可以使用 Counter 进行以下操作：

from operator import itemgetter

from collections import Counter

def most_common_name(l):

    counts = Counter(l)

    r, _ = max(counts.items(), key=itemgetter(1))

    return r

result = 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 Counter

def mostCommonName(L):

    return Counter(L).most_common(1)[0][0]