9.1-1

一、题目描述

证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）

补充说明：

(1)这里的比较是只元素之间的比较。下标的比较是不算在内的。

(2)ceil是向上取整的意思

二、常规方法

算法过程

使用两次for循环，分别将数组从前往后扫描。

第一次扫描过程中，不断记录和更新当前情况下的最小元素。

第二次扫描过程中，不断记录和更新当前情况下的第二小元素。

伪代码如下：

def findSmallest( array ) :
    smallest, smallestId = array[0], 0
    array = array[ 1 : ]
    for index, element in enumerate ( array ) :
        if element < smallest :
            smallest, smallestId = element, index
    return smallestId

def findSecondSmaller( array, minId ) :
    array = array[ : minId ] + array[ minId+1 : ]
    array = array[ 1 : ]
    secondSmaller = array[0]
    for element in array :
        if element < secondSmaller :
            secondSmaller = element
    return secondSmaller

def solution ( array ) :
    smallestId = findSmallest( array )
    smaller = findSmaller ( array, smallestId )
    return smaller

array = [12, 34, 56]
print solution( array )

常规方法的比较次数

第一个循环过程中，每次循环内部的比较次数为1次，循环次数即扫描的元素个数为n-1，因此比较第一次循环过程的次数是n-1。

第二个循环过程中，每次循环内部的比较次数也是1次，循环次数即扫描的元素个数为n-2（去去掉了最小元素），因此比较第二次循环过程的次数是n-2。

常规方法的比较次数为(n-1)+(n-2)，即2n-3次。

为了更直观地计算元素的比较次数，将元素的比较过程做了以下封装，除了完成比较操作以外，对用于计算比较次数的全局变量compareCnt加1

def compare(a, b) :
    global compareCnt
    compareCnt += 1
    return a < b

同时将findSmallest中的element < smallest替换为compare(element, small)，将findSmaller中的array[i] < sec替换为compare(array[i], sec)。并在调用sulution结束之后打印compareCnt。

三、方法改进一

在第一次循环求最小元素的过程时，对元素内容一无所知，因此n-1次的比较是必要的，难有优化空间。

在第二次循环求第二小元素的过程时，对元素的内容不再是一无所知。如果充分利用第一次循环所得到的信息，也许可以省掉第二次循环中不必要的比较。

本次优化的重点在第二次循环。

第一次循环的可用信息

假设数组中的元素为a, b, c, d, e, f, g … 。从前往后依次扫描

原理： 如果 a > b 且 b > c，那么不需要经过a和c的比较就可以知道 a > c。

信息1：

当扫描到元素d时，最小元素为c，可知 a > c, b > c, d > c。

当扫描到元素e时，最小元素变为了e，可知 e > c。

那么 a > c > e, b > c > e, d > c > e，

a,b,d不可能是第二小元素或最小元素

c是第二小元素，e是最小元素

信息2：

接着上文继续扫描，当扫描到元素g时，最小元素仍为e，可知f > e, g > e。

那么a > c > e, b > c > e, d > c > e, f > e, g > e

a, b, d不可能是第二小元素或最小元素

c, f, g有可能是第二小元素，e是最小元素

根据第一遍的可用信息作第二次循环

假设已经作过第一次扫描，找到了最小元素，为e，现在要充分利用第一次扫描的信息作第二次扫描。

这一次，我们并不是对除了e以外的所有元素扫描，而是只选择其中一部分。选择的依据来自于上一节的内容。

我们大胆猜测，第二小元素的候选值是那些在第一次扫描过程中与e做过直接比较的元素。

证明如下：

(1) 在第一次循环的过程中，第二小元素一定与最小元素e直接比较过。

证明：

第一种情况，在数组顺序中，第二小元素在e之前出现，在e出现之前，第二小元素一直都是被当作当前状态的最小元素，遇到e之后，因为与e比较失败，最小元素才变成了e。

第二种情况，在数组顺序中，第二小元素在e之后出现，那么e会与它后面出现的每一个元素直接比较。

(2) 与最小元素e直接比较过的元素都有可能是第二小元素

证明过程与1相反，略。

方法改进一的伪代码

第一次扫描的比较没有改变，只是每次比较的过程记录下来，以便第二次扫描的时候知道某个元素曾经和谁做过比较。

def findSmallestAndCollectInformation( array ) :
    comparePath = [ [] for i in range(len(array))]
    smallest, smallestId = array[0], 0
    array = array[ 1 : ]
    for index, element in enumerate ( array ) :
        if compare(element , smallest) :
            comparePath[index].append(smallest)
            smallest, smalleId = element, i
        else :
            comparePath[smallestId].append(element)
    return comparePath[smallestId]

第二次扫描时，仅取出最小元素所对应的队列元素做比较

def findSecondSmaller( comparePath ) :
    secondSmaller = comparePath[0]
    comparePath = comparePath [ 1 : ]
    for element in comparePath :
        if compare(element , secondSmaller) :
            secondSmaller = element
    return secondSmaller

方法改进一的比较次数

第一次扫描的次数仍然为n-1，主要差别在于第二次扫描。

第二次扫描也是FOR循环，每次循环内部的比较次数是1次，总的比较次数取决于 队列中元素的个数。假设个数为m，那么比较次数为m-1。

为了计算m，我画了这样一个图。叶子结点为数组中的元素。没有标字母的节点表示其它两个孩子结点的比较结果。画出这样的图，任假设一个结点为最小元素，都能很清晰地看出其队列中元素的个数。 我们取两种最极端的情况：

假如最小元素为A，那么其队列中的元素为B, C, D这3个元素

假如最小元素为D，那么其队列中的元素为A, B, C中最小的那1个元素。

结论，方法改进一的比较次数最多为2n-3，最少为n-1，取决于最小元素所在位置。

四、方法改进二

虽然方法改进一相比于常规方法是有了改善，但最多比较次数仍然需要2n-3次，未达到题目所要求。这次我们方找最小元素的过程入手。

上文已经说过，求最元素的过程到少要经过n-1次比较，这一点是难以改变的。但我们仍可以通过调整第一次遍历方式，使留给第二次遍历更多有用的信息。

二叉树的平衡化

根据上文可知，方法改进一的比较次数主要取决于第一次扫描过程中与最小元素直接比较的元素的个数。

由于第一次扫描是从前往依次扫描的，如果最小元素刚好是第一个元素，那么它后面的每一个元素都要与它一一比较，就是最坏情况。

要想减少最坏情况的比较次数，就是不管最小元素出现在什么位置，与它直接比较的元素都不能太多，也就是尽量让每个元素与其它元素的比较次数平均化。仍然以上文的图为例： 方法改进一的第一次遍历可以画成这一样的图，数组中的每一元素是这个二叉树的叶子结点。假如某一个元素是最小元素，那么它的队列的元素即该叶子结点的高度。

这棵二叉树明显不平衡，左重右轻的感觉。只要将树平均化，如下图所示，保证每一个叶子的高度都不会太高，那么每个元素对应的队列都就不会太大。

注意，这里所说的二叉树的平衡化，与平衡二叉树没什么关系，只是让二叉树的结点分布均匀，降低树的高度。 这种二叉树的比较策略不再是从头开始一个一个地比较。而地每两个一组进行比较，胜出者进入一轮，再两个一组的比较，若某一轮中元素个数为奇数，则有一个元素轮空，直接晋级。直到剩下最后一个元素。

这种比较规则类似于比赛中的淘汰制。

当然，比较的同时，胜者仍然要记录它跟谁比较过。

方法改进二的伪代码

为了代码实现方便，这里并不是按照图中所画的A和B比较，C和D比较，而是首尾比较，第一个和最后一个，第二个和倒数第二个……

def findSmallestAndCollectInformation( array ) :
    indexList = [ i for i in range(len(array)) ]
    comparePath = [ [] for i in range(len(array)) ]
    while len(indexList) != 1 :
        indexList = compareAndStore(array, indexList, comparePath)
    return comparePath[indexList[0]]

def compareAndStore(array, indexList, comparePath) :
    tempIndexList = []
    indexCount = len( indexList )
    for i in range( int((indexCount)/2) ) :
        f = lambda : indexCount-i-1
        if compare ( array[indexList[i]] , array[indexList[f()]] ) :
            comparePath[indexList[i]].append(array[indexList[f()]])
            tempIndexList.append(indexList[i])
        else :
            comparePath[indexList[f()]].append(array[indexList[i]])
            tempIndexList.append(indexList[f()])
    if indexCount % 2 != 0 :
        tempIndexList.append(indexList[int(indexCount/2)])
    return tempIndexList

方法改进二的比较次数

对于第一次遍历，比较次数仍为n-1。

对于第二次遍历，比较次数取决于第一次遍历转化生成的二叉树的高度h。 将二叉树平均化以后，树的高度为h= ceil[lgn]。

结论，方法改进二的比较次数最多为n+ ceil[lgn]-2。

五、总结

本题先从常规方法分析，使用两个遍历计算出结果。

在优化过程中，首先通过第一次遍历得到的信息优化第二遍历的过程，然后通过修改第一次遍历的顺序以得到更多的可用信息。

本题主要难点在于将比较过得转换成树来思考。有一点tips，题目中提到了ceil(lgn)，类似于这样的计算公式通常与树有关，进一步说，通过与完全二叉树的高度有关。一开始就往这方面去想，就比较容易了。

六、代码

产品代码 测试代码