Python实现马拉松未完赛参赛者查询函数的问题与优化咨询

首先，你的代码在小规模测试用例下能得到正确结果，但存在两个核心问题：

1. 时间效率极低，无法处理10万级别的数据 #

每次if i in participant是O(n)的查找操作，participant.remove(i)也是O(n)的删除操作，当参赛人数达到10万时，整体时间复杂度会飙升至O(n²)，直接导致程序超时，根本无法完成计算。

2. 返回值逻辑错误 #

你把print()的结果赋值给了answer，但print()函数的返回值是None，所以你的函数最终返回的是None，而非题目要求的未完赛者字符串。正确的逻辑应该是返回结果，而非直接打印（除非题目明确要求输出到控制台，但示例显示需要返回目标字符串）。

针对这个问题，有几种不同风格但都远优于当前方案的实现：

方法1：哈希表统计次数（最优时间复杂度O(n)） #

通过字典统计每个名字的出现次数，参赛列表遍历计数+1，完赛列表遍历计数-1，最后找到计数为1的名字即可：

def solution(participant, completion):
    count = {}
    # 统计参赛选手出现次数
    for name in participant:
        count[name] = count.get(name, 0) + 1
    # 减去完赛选手的次数
    for name in completion:
        count[name] -= 1
    # 找到次数为1的未完成选手
    for name, cnt in count.items():
        if cnt == 1:
            return f'"{name}"'

方法2：排序后对比（代码简洁，时间复杂度O(n log n)） #

将两个列表排序后，逐个对比元素，第一个不匹配的参赛选手就是未完赛者；如果前面全部匹配，那最后一位参赛选手就是目标：

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return f'"{p}"'
    # 前面全匹配时，最后一位参赛选手未完成
    return f'"{participant[-1]}"'

方法3：用collections.Counter（最简洁的Pythonic写法） #

Python内置的Counter类支持直接做集合减法，结果就是仅在参赛列表中多出现一次的名字：

from collections import Counter

def solution(participant, completion):
    diff = Counter(participant) - Counter(completion)
    return f'"{next(iter(diff.keys()))}"'

测试验证：

• 针对你的示例participant = ["john", "mike"]，completion = ["john"]，三种方法都会返回"mike"，符合预期。
• 针对重名场景participant = ["a", "a", "b"]，completion = ["a", "b"]，也能正确返回"a"。

内容的提问来源于stack exchange，提问作者cycla