减少列表遍历器的执行时间

Question

我正在进行编码练习。我的逻辑是有道理的，但是在一个大列表上超出了执行限制。这是问题描述：

Given an array of the numbers of votes given to each of the candidates so far, and an integer k equal to the number of voters who haven't cast their vote yet, find the number of candidates who still have a chance to win the election.

The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same (maximum) number of votes, assume there is no winner at all.

Example

For votes = [2, 3, 5, 2] and k = 3, the output should be electionsWinners(votes, k) = 2.

The first candidate got 2 votes. Even if all of the remaining 3 candidates vote for him, he will still have only 5 votes, i.e. the same number as the third candidate, so there will be no winner. The second candidate can win if all the remaining candidates vote for him (3 + 3 = 6 > 5). The third candidate can win even if none of the remaining candidates vote for him. For example, if each of the remaining voters cast their votes for each of his opponents, he will still be the winner (the votes array will thus be [3, 4, 5, 3]). The last candidate can't win no matter what (for the same reason as the first candidate). Thus, only 2 candidates can win (the second and the third), which is the answer.

这是我的逻辑。我知道，对于这个问题，我必须遍历列表中的每个元素，看看添加 k 是否会使它成为列表中的最大值。但我也觉得我必须检查列表中该值的出现次数才能正确识别是否有赢家或平局：

def electionsWinners(votes, k):
    
    # This variable basically counts the number of possible winners in the list
    counter = 0
    
    for i in votes:
        
        # If all votes go into candidate i and its not a tie:
        if k + i > max(votes) and votes.count(k + i) <= 1:
            # Increment one because we have a potential winner
            counter += 1
        
        # If there are no remaining votes and the biggest value of the list only occures once
        elif k == 0 and votes.count(max(votes)) == 1:
            
            # We only have one winner
            counter = 1
    
    return counter

我知道我使用 list.max() 和 list.count() 会增加执行时间。有哪些方法可以使此代码运行更快？

虽然我感谢所有的帮助，但看到人们只发布一个简单的答案是非常令人沮丧的。这不是家庭作业。它意味着练习，所以你给我答案对我一点帮助都没有。让我知道如何修复我现有的代码。提前谢谢大家。

Answer 1

一些可以优化的东西：

max(votes) 不依赖于 i 的值，因此不应在每次循环迭代中对其求值。在循环开始前计算一次。
表达式k == 0 and votes.count(max(votes)) == 1也是如此。它不依赖于循环变量，所以它不应该出现在循环中。应该成为循环是否执行的条件
k + i > max(votes) and votes.count(k + i) <= 1：如果条件的第一部分为真，则条件的第二部分永远为真。当 k + i 大于列表中的最大值时，该总和不会出现在列表中，即计数将为零。

所以把所有这些放在一起，你可以写成：

def electionsWinners(votes, k):
    greatest = max(votes)
    if k == 0:
        if votes.count(greatest) == 1:
            return 1
        else:
            return 0

    counter = 0
    for i in votes:
        if k + i > greatest:
            counter += 1
    
    return counter

您可以通过使用 sum 代替“手动”counter += 1 获得一些微小的收益。同时代码也可以减少一点：

def electionsWinners(votes, k):
    greatest = max(votes)
    if k == 0:
        return int(votes.count(greatest) == 1)

    return sum(1 for i in votes if k + i > greatest)

甚至：

def electionsWinners(votes, k):
    mx = max(votes)
    return sum(1 for i in votes if k + i > mx) if k else int(votes.count(mx) == 1)

减少列表遍历器的执行时间

Reducing the execution time of a list traverser

python

algorithm

execution-time