一、问题描述
给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 **answer ：
answer[0]是所有 没有 输掉任何比赛的玩家列表。answer[1]是所有恰好输掉 一场 比赛的玩家列表。
两个列表中的值都应该按 递增 顺序返回。
注意：
- 只考虑那些参与 至少一场 比赛的玩家。
- 生成的测试用例保证 不存在 两场比赛结果 相同 。
题目链接：输掉零场或一场比赛的玩家
二、题目要求
样例
输入： matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]] 输出： [[1,2,10],[4,5,7,8]] 解释： 玩家 1、2 和 10 都没有输掉任何比赛。 玩家 4、5、7 和 8 每个都输掉一场比赛。 玩家 3、6 和 9 每个都输掉两场比赛。 因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。
考察
哈希、判重 建议用时15~35min
三、问题分析
这一题其实很好理解，一开始我的想法是用哈希表统计输掉比赛的人。
输掉0场就只判断赢得比赛的玩家在不在里面就行，输掉一场直接在判断哈希表的值为1就行。
但这种方法有个缺陷，执行用时太长了，还需要对赢得人进行判重操作，防止重复加入。
开始优化！
map可以自动排序，所以这次利用map输出存储。我们先存储赢的玩家到map，初始值置为0。再存储输的玩家到map，这时候我们只需要判断0 1就行。
四、编码实现
1.优化前
classSolution { public: vector<vector<int>>findWinners(vector<vector<int>>&matches) { map<int,int>l,k;//map存储输掉比赛的人数inti,j,m=matches.size();//初始化数据vector<int>ans1,ans2;//分别存储for(i=0;i<m;i++) l[matches[i][1]]++;//记录输掉比赛的人数for(i=0;i<m;i++) { if(l[matches[i][0]]==0&&k[matches[i][0]]==0)//没有输 { ans1.push_back(matches[i][0]); k[matches[i][0]]=1;//用来判重 } if(l[matches[i][1]]==1&&k[matches[i][1]]==0)//只输一场 { ans2.push_back(matches[i][1]); k[matches[i][1]]=1;//用来判重 } } sort(ans1.begin(),ans1.end());//排序sort(ans2.begin(),ans2.end());//排序return {ans1,ans2};//输出结果 } };
2.优化后
classSolution { public: vector<vector<int>>findWinners(vector<vector<int>>&matches) { map<int,int>m;//定义mapvector<int>ans1,ans2; inti,n=matches.size();//初始数据for(i=0;i<n;i++)//存储赢得人数、置为0m[matches[i][0]]=0; for(i=0;i<n;i++)//存储输人数++m[matches[i][1]]++; for(autoj=m.begin();j!=m.end();j++)//在map循环内部存储输出 { if(j->second==0)//为0ans1.push_back(j->first);//存储没输的玩家elseif(j->second==1)//为1ans2.push_back(j->first);//存储只输一场的玩家 } return {ans1,ans2}; } };
