第二个或最后一个

Second or last but one

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

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

None这六个元素的值相同.

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

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

首先如果你想从列表或数组中找到第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 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 没有被取代)。在两个比较中找到最好的。

一个简单但不是最佳的方法是使用冒泡排序的前两遍:这将交换变量对,因此将 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 次比较