给出一系列选手的比赛结果,list中每一组[a,b]表示该场比赛选手a赢了选手b,统计所有比赛(1 <= matches.length <= 10
5),输出没有输过的选手ID list和只输了一次的选手list,注意输出的选手ID需要排序,用python的set和dict随便写了一下,速度和内存都很一般,第一种写法用set记录所有选手的ID,用dict记录每一个输过的选手的输额度次数,在第二重循环统计只输了一场的选手时,顺便从选手列表remove掉出现在loser字典里的选手;第二种写法多用一个set记录输过的选手id,用差集计算出没有输过的选手ID
1 #2225
2 #Runtime: 3559 ms
3 #Memory Usage: 76.9 MB
4
5 class Solution(object):
6 def findWinners(self, matches):
7 """
8 :type matches: List[List[int]]
9 :rtype: List[List[int]]
10 """
11 players = set()
12 losers_dct = {}
13 lost_once = []
14 for [a, b] in matches:
15 players.add(a)
16 players.add(b)
17 if b not in losers_dct:
18 losers_dct[b] = 1
19 else:
20 losers_dct[b] += 1
21 for i in losers_dct:
22 players.remove(i)
23 if losers_dct[i] == 1:
24 lost_once.append(i)
25 return [sorted(players), sorted(lost_once)]
1 #2225
2 #Runtime: 3981 ms
3 #Memory Usage: 74.2 MB
4
5 class Solution(object):
6 def findWinners(self, matches):
7 """
8 :type matches: List[List[int]]
9 :rtype: List[List[int]]
10 """
11 players = set()
12 losers = set()
13 losers_dct = {}
14 lost_once = []
15 for [a, b] in matches:
16 players.add(a)
17 players.add(b)
18 losers.add(b)
19 if b not in losers_dct:
20 losers_dct[b] = 1
21 else:
22 losers_dct[b] += 1
23 winners = list(players - losers)
24 for i in losers_dct:
25 if losers_dct[i] == 1:
26 lost_once.append(i)
27 return [sorted(winners), sorted(lost_once)]