HJ94 记票统计 题解

by 限时烟花

抽丝剥茧

这是一道比较初级的入门题，主要考查的是对于输入的正确捕获和一些判断。整体难度是比较简单的。

化繁为简

利用python中的split函数很容易地可以得到候选人列表和投票列表。

在获得候选人和投票的列表之后，我们只需要对投票的结果进行遍历，并对每一个选票判断是否在候选人的列表中即可。

码上行动

while True:
    try:
        num_cand, cands, num_vote, votes = input(), input().split(), input(), input().split()
        res = { cand : 0 for cand in cands}
        res['Invalid'] = 0
        for v in votes:
            if v in cands:
                res[v] += 1
            else:
                res['Invalid'] += 1
        for i in res.keys():
            if i != 'Invalid':
                print(i + " : " + str(res[i]))
        print("Invalid : " + str(res['Invalid']))
    except:
        break

心有成算

假设有m个候选人，有n个投票：

时间复杂度：由于需要对每一个投票判断是否符合候选人的名字，故时间复杂度为$O(mn)O(mn)$

空间复杂度：由于使用了常数级别的临时变量，故空间复杂度为$O(1)O(1)$

例题图解

另辟蹊径

我们可以做出效率的解答： 我们分析可以发现，整体的解题思路非常直接，基本没有可以简化的地方。 为数不多的地方就是在判断选票是否在候选人列表中，这里如果是采用列表结构，那时间复杂度就是$O(n)O(n)$，但是如果使用hash表来判断，那么就可以在$O(1)O(1)$的时间内得出结果。 故我们采用“空间换时间”的思路，使用defaultdict建立一个cands的hash表，当我们需要进行判断时（下列代码12行），一方面由于使用的是defaultdict，避免了报错，另一方面，由于hash表的作用提高了效率。

from collections import defaultdict

while True:
    try:
        num_cand, cands, num_vote, votes = input(), input().split(), input(), input().split()
        res = { cand: 0 for cand in cands}
        res['Invalid'] = 0
        tmp = defaultdict(int)
        for cand in cands:
            tmp[cand] = 1
        for v in votes:
            if tmp[v] == 1:
                res[v] += 1
            else:
                res['Invalid'] += 1
        for i in res.keys():
            if i != 'Invalid':
                print(i + " : " + str(res[i]))
        print("Invalid : " + str(res['Invalid']))
    except:
        break

假设有m个候选人，有n个投票：

时间复杂度：由于hash表的优化，时间复杂度降为$O(m)O(m)$

空间复杂度：由于需要tmp数组，其长度为投票大小，故空间复杂度为$O(n)O(n)$