Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一系列选手的比赛结果,list中每一组[a,b]表示该场比赛选手a赢了选手b,统计所有比赛(1 <= matches.length <= 105),输出没有输过的选手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)]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理