Wise OA 面试真题解析：即时淘汰投票（Instant-Runoff Voting）获胜者

题目描述

给定每个选民的候选人排序选票，实现即时淘汰投票（IRV）：每一轮统计当前存活候选人的第一选择得票，淘汰得票最少者，把其选票转移给该选票上的下一个存活候选人，直到有候选人获得多数或只剩一人。

解题思路

按轮次模拟。每轮遍历所有选票，找到选票上第一个仍存活的候选人并计票；找出得票最少的候选人淘汰（并列时按题意规则打破）。重复直到出现多数赢家或只剩一个候选人。

def irv_winner(ballots, candidates):
    alive = set(candidates)
    while True:
        counts = {c: 0 for c in alive}
        for ballot in ballots:
            for c in ballot:
                if c in alive:
                    counts[c] += 1
                    break
        total = sum(counts.values())
        for c, v in counts.items():
            if v * 2 > total:
                return c
        if len(alive) == 1:
            return next(iter(alive))
        loser = min(counts, key=lambda c: (counts[c], candidates.index(c)))
        alive.remove(loser)

复杂度与易错点

每轮扫描所有选票，O(轮数 × 选票总长度)。并列最少得票时如何淘汰要按题面规则（如按候选注册顺序）；某轮出现平局无法推进时也要有明确出口，避免死循环。

FAQ

并列最少得票时该淘汰谁？

题面通常规定一个确定性的打破规则（如按候选注册顺序淘汰最靠后者）。没有规则时结果不可复现，实现前要先确认。

参考来源

• LeetCode 1366 — Rank Teams by Votes
• LeetCode 911 — Online Election

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。