第二个或最后一个

Question

通过 IT 国际公司的代码面试，我运行遇到了一个有趣的问题。

我们需要进行多少次比较才能找出六个中的哪个元素是第二小的或[=33] =]第二大.

None这六个元素的值相同.

我们有一个带有六个参数的 main 函数 (v1, ..., v6)

 def solve(v1, v2, v3, v4, v5, v6):
     # the worst case -> 9 comparisons
     if isLarger(v1, v2):
         v1, v2 = v2, v1
     if isLarger(v1, v3):
         v1, v3 = v3, v1
     if isLarger(v1, v4):
         v1, v4 = v4, v1
     if isLarger(v1, v5):
         v1, v5 = v5, v1
     if isLarger(v1, v6):
         v1, v6 = v6, v1
     if isLarger(v2, v3):
         v2, v3 = v3, v2
     if isLarger(v2, v4):
         v2, v4 = v4, v2
     if isLarger(v2, v5):
         v2, v5 = v5, v2
     if isLarger(v2, v6):
         v2, v6 = v6, v2
     print(f"#comparisons = {CntComparisons}")
     return v2

哪个returns第二小或者第二大的值。

通过比较确定这个值（即它不能使用该值的索引）。

对于成对比较，我们只能使用下面的函数

CntComparisons = 0
def isLarger(v1, v2):
    global CntComparisons
    CntComparisons += 1
    return v1 > v2

仅通过调用比较函数isLarger(v1, v2).
来比较值

我们的目标是找到一种需要（即使在最坏的情况下）尽可能少的比较的算法！

任何想法或提示如何解决这个问题？

Answer 1

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

天真（随意的方法）
巧妙的方法（现代方法）

比较幼稚的方法就是排序k次后每次弹出元素。就像，

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

Answer 2

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

通过安排淘汰赛，您可以保证最多有 log n 名候选人进入 第二名 ，并且从他们中找到最好的需要 log 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, v4（或者只是 v2, v4，如果领导者 v1 没有被取代）。在两个比较中找到最好的。

Answer 3

一个简单但不是最佳的方法是使用冒泡排序的前两遍：这将交换变量对，因此将 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。 Return v1 和 vx 中最大的：这需要另一个，第 7^次比较。
如果在这些布尔结果中只有一个 False（即 v2 大于其中两个），则令 vx 为 v3、v4 或 v5 中 v2 不大于的那个vx。 Returnv3和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 次比较

第二个或最后一个

Second or last but one

python

python-3.x

algorithm

comparison