algorithm - 找到给定 K 个最佳候选者的时间戳

Question

所以我被问到 K 最佳候选人问题的奇怪反转。正常问题如下。

给定一个“投票”列表，它是时间戳和候选人的元组，如下所示:

(111111, Clinton)
(111111, Bush)
...

返回得票最多的前 K 个候选人。

这是一个典型的问题，解决方案是使用候选人的 HashMap ->在时间戳范围内投票还构建了一个大小为 K 的最小堆，其中基本上堆的顶部是容易被逐出的候选人K最佳人选。

最后你返回堆。

但最后有人问我:给定 K 个候选人的列表，返回与这些匹配的时间戳作为 K 个最佳候选人。我不确定我是否 100% 正确地记忆了这个问题，因为它必须是这 K 个候选人中第一次出现的最佳人选，否则我会得到他们的票数。

Answer 1

如果我理解一切，votes 是一个投票元组列表，由被投票的候选人和投票发生的时间戳组成。 currTime 是在它之前的那个时间戳期间所有投票的时间戳。 topCandidates 是在 currTime 获得最高票数的候选人。

你的第一个问题给了你votes和currTime，你应该返回topCandidates。你的第二个问题给你 votes 和 topCandidates，你应该返回 currTime。

针对第二个问题，我会制作一张 map ，其中键是时间戳，值是当时发生的所有投票。另外我会创建另一个 map ，其中键是候选人，值是他们到目前为止的票数。我将按照第一张 map 的升序时间戳顺序遍历第一张 map ，获得在时间戳上投下的所有选票，然后将第二张 map 的值增加他们的候选人(键)。在查看下一个时间戳之前，我将使用第二张 map 中的数据创建一个投票最多的候选人列表。如果该列表匹配 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 looks to be O(n*log(k))它可以运行 t 次。不过肯定有更有效的答案。