我最近在一次电话采访中被问到了这个问题.
"有一个元素列表.你必须从列表中找到" 最佳 "元素.这些元素相互比较,但比较不具有传递性.例如,如果A> B和B> C,那么A需要不大于C.
您必须返回最佳元素作为答案,这比列表中的每个其他元素都要好.有可能,没有这样的元素.在这种情况下,返回null."
我的解决方案
尝试1:
一个简单的O(n ^ 2)解决方案.每个元素与彼此元素的比较.
面试官不满意.
尝试2:
开始将第一个元素与第二个元素进行比较.对于任何元素"E",如果A> E,则标记E(可以使用另一个数组/列表/等),并且不考虑E进行任何进一步的比较.这是因为至少有一个元素比E好,所以E绝对不是答案.
复杂性仍然是O(n ^ 2),与之前的尝试相比有一些改进.
他仍然不满意.任何人都可以提出更好的解决方案吗？
Dan*_*Dan 18
当然.你有N个元素.比较前两个.其中一个比另一个"更糟糕".丢弃它.将两者中的"更好"与下一个元素进行比较.继续第一遍整个列表,直到只剩下一个元素.该步骤是O(N).
现在需要将第一遍中幸存的一个元素与原始列表中的每个元素进行比较,除了那些已经与之比较的元素.如果它"丢失"甚至一次,你就会发现没有"最佳"元素.如果它在此步骤中"赢得"每个比较,则返回此元素.该步骤也是O(N).
该算法在最坏情况下为O(N + N)= O(N),在最佳情况下为O(N + 0)== O(N).我们可以进一步证明这是最好的复杂性,因为检查解决方案也是O(N),并且获得解决方案比检查解决方案要简单得多.