puzzle - 从给定的列表中找到 'Best' 元素

Question

我最近在一次电话采访中被问到这个问题。

“有一个元素列表。你必须找到” 最好的 "列表中的元素。元素可以相互比较，但 比较不是传递的 。
例如。如果 A > B 且 B > C，则 A 不必大于 C。

您必须返回最佳元素作为答案，这比列表中的所有其他元素都要好。有可能没有这样的元素。在这种情况下，返回 null。”

我的解决方案:

尝试 1:

一个简单的 O(n^2) 解决方案。每个元素与其他元素的比较。

面试官不满意。

尝试 2:

开始比较第一个元素与第二个元素及以后的元素。对于任何元素“E”，如果 A > E，标记 E(可能是通过使用另一个数组/列表/等)并且不考虑 E 进行任何进一步的比较。这是因为至少有 1 个元素比 E 更好，所以 E 绝对不是答案。

复杂性依旧 O(n^2) 与之前的尝试相比有一些改进。

他还是不满意。谁能想出更好的解决方案？

Answer 1

当然。你有 N 个元素。比较前两个。其中之一比另一个“更糟”。丢弃它。将两者中的“更好”与下一个元素进行比较。继续第一次遍历列表，直到只剩下一个元素。这一步是 O(N)。

在第一遍中幸存下来的一个元素现在需要与原始列表中的每个元素进行比较，除了那些已经与之比较的元素。如果它“输了”一次，您会返回没有“最佳”元素。如果它在此步骤中“赢得”每一次比较，则返回此元素。这一步也是 O(N)。

该算法在最坏情况下为 O(N+N) = O(N)，在最佳情况下为 O(N+0) == O(N)。我们可以进一步证明这是最好的可能复杂度，因为检查一个解决方案也是 O(N)，并且获得一个解决方案不可能比检查它更复杂。