1

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

给定一个“投票”列表，这些“投票”是时间戳和候选者的元组，如下所示：

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

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

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

最后你返回堆。

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

4

1 回答 1

0

如果我理解所有内容，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时间。不过，肯定有更有效的答案。

于 2018-05-27T23:46:03.907 回答