欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

怎么在一次循环内找出一个数组最小的2个数

程序员文章站 2024-03-16 18:42:04
...

在写哈夫曼树的时候卡在了怎么找出最小的2个节点这个问题上,所以专门写一篇来讨论下怎么实现一次循环找出来

我们先来实现找出1个最小值的方法

L=[6,4,7,3,7,2,9,3,1,5,3]
    m1=m2=L[0]
    for x in range(0,len(L)):
        if m1>L[x]:
            m1=L[x]

现在再加入一个变量m2,既然每次比较后m1会变小,那我们每次比较后给m1赋值前把前一个m1给赋值给m2是不是可以呢?

L=[6,4,7,3,7,2,9,3,1,5,3]
    m1=m2=L[0]
    for x in range(0,len(L)):
        if m1>L[x]:
            m2=m1
            m1=L[x]
    print m1,m2

结果如何?

怎么在一次循环内找出一个数组最小的2个数

 看似稳了,但我们换组数据试试

L=[9,8,7,5,1,4,2,3]
    m1=m2=L[0]
    for x in range(0,len(L)):
        if m1>L[x]:
            m2=m1
            m1=L[x]
    print m1,m2

结果呢?

怎么在一次循环内找出一个数组最小的2个数

 发现存在问题,为什么呢?

m2值的改变是依赖于后面有比m1小的数,如果是图上这种2在1后面的情况,m1跳过了和1的比较,所以我们还需要给m2加一个比较过程。

L=[9,8,7,5,1,4,2,3]
    m1=m2=L[0]
    for x in range(0,len(L)):
        if m1>L[x]:
            m2=m1
            m1=L[x]
        elif m2>L[x]:
            m2=L[x]
    print m1,m2

这下就算完成了,测试之后也是正确的,但是这样确定没问题了吗?

L=[1,2,3,4,5,6,7]
    m1=m2=L[0]
    for x in range(0,len(L)):
        if m1>L[x]:
            m2=m1
            m1=L[x]
        elif m2>L[x]:
            m2=L[x]
    print m1,m2

我们来看看这组数据的测试结果

怎么在一次循环内找出一个数组最小的2个数

 加入一开始m1和m2就是最小的,那么m2的判断将会无法生效,现在来想想怎么解决。

其实这里的逻辑本身已经没有问题了,因为比较最小值的过程本身就是找出小的数,所以我们这里不改变逻辑,

选择把m1和m2的初始值变成一个极大的数,这样就能避免这个问题的发生。

# -*- coding: utf-8 -*-

if __name__=='__main__':
    L = [1, 2, 3, 4, 5, 6, 7]
    m1 = m2 = float('inf')
    for x in range(0, len(L)):
        if m1 > L[x]:
            m2 = m1
            m1 = L[x]
        elif m2 > L[x]:
            m2 = L[x]
    print m1, m2

测试结果如下

怎么在一次循环内找出一个数组最小的2个数

 这样就算彻底完成了,本来以为很快就能完成的极简的计算方法居然都有这么多坑,这件事也是提醒我们

写程序一定要谨慎。