第二个或最后一个，但一个

首先，如果要从列表或数组中找到第 k 个最大或第 k 个最小元素，主要有两种方法

1. 幼稚（随意方法）
2. 巧妙的方法（现代方法）

朴素的方法是在排序 k 次后每次弹出元素。 它是这样说的，

def myfun(l):
    for i in range(k):
        l=sorted(l)
        l.pop()
    return sorted(l)[0]

找到最佳元素总是需要比较。第二好的元素是那些只输给最好的元素的人。n-1

通过安排淘汰赛，您可以保证最多有第二名的候选人，并在其中找到最好的进行比较。log nlog n

因此，对于 6 个元素，您需要 5 + 2 = 7 个比较。

在代码中表达这一点时，这里是第一轮淘汰：

if isLarger(v1, v4):
    v1, v4 = v4, v1
if isLarger(v2, v5):
    v2, v5 = v5, v2
if isLarger(v3, v6):
    v3, v6 = v6, v3

现在接下来的两场比赛有点棘手。您还必须交换第一轮中相应的输家，例如

if isLarger(v2, v3):
    v2, v3 = v3, v2
    v5, v6 = v6, v5

以保持不变量，如 。v2 < v5

在那之后，候选人是（或者只是，如果领导者没有被取代）。在两次比较中，找到其中最好的。v2, v3, v4v2, v4v1

一个微不足道但不是最佳的方法是使用冒泡排序的前两次传递：这将交换变量对，因此将 2 个最大值冒泡到“右边”并将它们分配给 v5 和 v6，因此 v5 将作为正确答案返回。这需要 9 次比较：第一次 5 次比较，第二次 4 次比较。因此，我们有 9 个比较的上限。

下限是 5，因为这是找到最小值或最大值所需的比较次数，并且需要这样做才能确保值是次小值或次大值。

这里有一个想法：

• 执行 2 到 3 次比较，通过交换从小到大对 v1、v2、v3 进行排序。然后我们知道 v2 不是最小的，也不是最大的。

• 在 v2 和最后 3 个值（v3、v4 和 v5）之间执行 3 次比较。

• 如果这些比较都给出相同的布尔结果，则意味着 v2 确实是答案。

• 如果在这些布尔结果中只有一个 True（即 v2 仅大于其中一个），则让 vx 成为 v3、v4 或 v5 中 v2 大于 vx 的那个。返回最大的 v1 和 vx：这需要另一个第 7^个比较。

• 如果在这些布尔结果中只有一个 False（即 v2 大于其中两个），则让 vx 成为 v3、v4 或 v5 中 v2 不大于 vx 的那个。返回 v3 和 vx 中最少的：这需要另一个第 7^个比较。

因此，在最坏的情况下，我们通过 7 次比较得到结果。最好的情况需要 5 次比较（2 次用于排序步骤，c4、c5 和 c6）。

以下是这个想法的实现：

def solve(v1, v2, v3, v4, v5, v6):
    # Sort (v1, v2, v3)
    if isLarger(v1, v2):
        v1, v2 = v2, v1
    if isLarger(v2, v3):
        v2, v3 = v3, v2
        if isLarger(v1, v2):
            v1, v2 = v2, v1
    # v2 is now certainly not the greatest nor the least
    # Check how it compares with v4, v5 and v6
    c4 = isLarger(v2, v4)
    c5 = isLarger(v2, v5)
    c6 = isLarger(v2, v6)
    if c4 == c5 == c6:  # All true or all false
        return v2
    if c4 ^ c5 ^ c6:  # Only one of them is true
        vx = v4 if c4 else (v5 if c5 else v6)
        return v1 if isLarger(v1, vx) else vx
    else:  # Only one of them is false
        vx = v4 if not c4 else (v5 if not c5 else v6)
        return vx if isLarger(v3, vx) else v3

我在所有排列上运行了这个，结果是：[1,2,3,4,5,6]

• 96 次渗透需要 5 次比较
• 336 种排列需要 6 次比较
• 288 种排列需要 7 次比较

平均： 6.266667 比较