所以我被问到K最佳候选人问题的奇怪反转。正常问题如下。
给定一个"投票"列表，这些"投票"是时间戳和候选人的元组，如下所示：
(111111, Clinton)
(111111, Bush)
...
返回得票最多的前 K 名候选人。
这是一个典型的问题，解决方案是在时间戳范围内使用候选人>投票的哈希图，并构建一个大小为 K 的最小堆，其中基本上堆的顶部是容易被从 K 最佳候选人中弹出的候选人。
最后，您返回堆。
但最后有人问我：给定一个 K 个候选者的列表，返回与这些候选者匹配的时间戳作为 K 个最佳候选项。我不确定我是否 100% 正确地回忆了这个问题，因为它必须是这些 K 候选人的第一次出现，否则我就会得到他们的选票统计。
如果我了解所有内容，votes是一个投票元组列表，这些元组由正在投票的候选人和投票的时间戳组成。currTime是之前该时间戳内所有投票的时间戳。topCandidates是currTime得票最高的候选人。
您的第一个问题为您提供votes和currTime，您应该返回topCandidates。你的第二个问题给你votes和topCandidates，你应该返回currTime。
专注于第二个问题，我会制作一张地图，其中键是时间戳，值是当时发生的所有投票。我还会创建另一张地图，其中键是候选人，值是他们迄今为止的票数。我将按照第一个地图的时间戳升序遍历第一个地图，获取在时间戳上投下的所有选票，并按其候选(键(递增第二个地图的值。在浏览下一个时间戳之前，我会使用第二张地图中的数据创建一个投票最多的候选人列表。如果该列表与topCandidates匹配，则您遍历的最后一个时间戳为currTime。
要用python编写代码：
from collections import Counter, defaultdict
def findCurrTime(votes, topCandidates):
if not (votes and topCandidates):
return -1
votesAtTime = defaultdict(list)
candidatePoll = Counter()
k = len(topCandidates)
for time, candidate in votes: # votes = [(time0, candidate0), ...]
votesAtTime[time].append(candidate)
for ts in votesAtTime:
candidatePoll += Counter(voteAtTime[ts])
if list(map(lambda pair: pair[0],candidatePoll.most_common(k))) == topCandidates:
return ts
# if topCandidates cannot be created from these votes:
return -1
我做了一些假设(你希望问过你的面试官(。我假设topCandidates的顺序很重要，Counter.most_common处理哪个，尽管它不会处理有票数的候选人。
时间复杂度为 O(t * n * log(k((，其中 t 是时间戳数，n 是票数，k 是topCandidates的大小。这是因为Counter.most_common看起来是O(n*log(k((，它可以运行t次。不过，肯定有更有效的答案。