首页 / 问题 / 正文

从包含100,000个整数的列表中获取两个最大值

47 投票
16 回答
49993 浏览
提问于 2025-04-15 22:10

如何在一个包含100,000个整数的列表中，不用先把整个列表排序，就能找到两个最大的数字呢？

数据结构 算法 最大值查找

16 个回答

6

你可以遍历这个列表，同时保持两个变量，一个用来存储目前为止遇到的最大值，另一个用来存储第二大值。每当遇到一个新值时，如果这个新值比这两个值中的任何一个都大，就用这个新值替换掉较小的那个。

回答于 2025-04-15 由 Python大师
分享 举报
19

JacobM的回答确实是个好主意。不过，在实现他所描述的内容时，有一些事情需要注意。下面是一个简单的教程，帮助你解决这个问题中比较棘手的部分。

如果这段代码是用于实际项目，请参考其他更高效或更简洁的答案。这个答案是针对编程新手的。

思路

这个思路很简单。

  • 保留两个变量：largest（最大值）和 second_largest（第二大值）。
  • 遍历这个列表。
    • 如果某个值大于 largest，就把它赋值给 largest。
    • 如果某个值大于 second_largest，但小于 largest，就把它赋值给 second_largest。

开始吧

让我们开始吧。

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

好的，现在我们有了JacobM的答案作为一个Python函数。那运行它会发生什么呢？

Traceback (most recent call last):
  File "twol.py", line 10, in <module>
    print two_largest(inlist)
  File "twol.py", line 3, in two_largest
    if item > largest:
UnboundLocalError: local variable 'largest' referenced before assignment

显然，我们需要在开始循环之前设置 largest。这可能意味着我们也应该设置 second_largest。

初始化变量

我们把 largest 和 second_largest 都设置为0。

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0 # NEW!
    second_largest = 0 # NEW!
    for item in inlist:
        if item > largest:
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [3, 2, 1]
    print two_largest(inlist)

很好。让我们运行它。

(3, 2)

太棒了！现在我们用 inlist 为 [1, 2, 3] 来测试一下。

    inlist = [1, 2, 3] # CHANGED!

让我们试试。

(3, 0)

...哎呀。

修正逻辑

最大值（3）看起来是正确的。但第二大值完全错了。发生了什么事？

让我们看看这个函数在做什么。

  • 当我们开始时，largest 是0，second_largest 也是0。
  • 我们查看的列表第一个值是1，所以 largest 变成1。
  • 下一个值是2，所以 largest 变成2。

但是 second_largest 呢？

当我们给 largest 赋新值时，原来的最大值实际上应该变成第二大值。我们需要在代码中体现这一点。

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = 0
    second_largest = 0
    for item in inlist:
        if item > largest:
            second_largest = largest # NEW!
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [1, 2, 3]
    print two_largest(inlist)

让我们运行它。

(3, 2)

太好了。

初始化变量，第二部分

现在我们用一组负数来试试。

    inlist = [-1, -2, -3] # CHANGED!

让我们运行它。

(0, 0)

这完全不对。这些零是从哪里来的？

原来 largest 和 second_largest 的初始值实际上比列表中的所有值都大。你可能会考虑把 largest 和 second_largest 设置为Python中可能的最小值。不幸的是，Python没有最小值。这意味着，即使你把它们都设置为-1,000,000,000,000,000,000，仍然可以有比这更小的值。

那么最好的办法是什么呢？我们可以尝试把 largest 和 second_largest 设置为列表中的第一个和第二个值。然后，为了避免重复计算，我们只查看第二个值之后的部分。

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    largest = inlist[0] # CHANGED!
    second_largest = inlist[1] # CHANGED!
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]: # CHANGED!
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-1, -2, -3]
    print two_largest(inlist)

让我们运行它。

(-1, -2)

很好！我们再试一组负数。

    inlist = [-3, -2, -1] # CHANGED!

让我们运行它。

(-1, -3)

等等，什么？

初始化变量，第三部分

让我们再检查一下我们的逻辑。

  • largest 被设置为 -3
  • second_largest 被设置为 -2

等等，这似乎不对。-2 比 -3 大。这是导致问题的原因吗？让我们继续。

  • largest 被设置为 -1；second_largest 被设置为旧的 largest 值，也就是 -3

是的，这看起来就是问题所在。我们需要确保 largest 和 second_largest 被正确设置。

def two_largest(inlist):
    """Return the two largest items in the sequence. The sequence must
    contain at least two items."""
    if inlist[0] > inlist[1]: # NEW
        largest = inlist[0]
        second_largest = inlist[1]
    else: # NEW
        largest = inlist[1] # NEW
        second_largest = inlist[0] # NEW
    # Only look at the part of inlist starting with item 2
    for item in inlist[2:]:
        if item > largest:
            second_largest = largest
            largest = item
        elif largest > item > second_largest:
            second_largest = item
    # Return the results as a tuple
    return largest, second_largest

# If we run this script, it will should find the two largest items and
# print those
if __name__ == "__main__":
    inlist = [-3, -2, -1]
    print two_largest(inlist)

让我们运行它。

(-1, -2)

太好了。

结论

所以这是代码，注释和格式都很清晰。我已经把我能找到的所有错误都修复了。希望你喜欢。

不过，如果这真的是一个作业问题，我希望你能从看到一段不完美的代码逐步改进中获得一些有用的经验。我希望这些技巧在你未来的编程作业中能派上用场。

效率

效率不是很高。但对于大多数情况来说，这应该没问题：在我的电脑上（Core 2 Duo），处理一个包含100,000个项目的列表大约需要0.27秒（使用 timeit，平均100次运行）。

回答于 2025-04-15 由 Python大师
分享 举报
68

使用 heapq.nlargest。这个方法非常灵活，如果你将来想处理的不仅仅是前两个元素，它会很有用。

下面是一个例子。

>>> import heapq
>>> import random
>>> x = range(100000)
>>> random.shuffle(x)
>>> heapq.nlargest(2, x)
[99999, 99998]
回答于 2025-04-15 由 Python大师
分享 举报

撰写回答