淘宝网站用什么语言做的,街景地图可移动,湖南土建网,如何进行网站建设的销售题目要求
给定一个整数数组 matches#xff0c;其中 matches[i] [winneri, Loseri] 表示玩家 Winneri 在一场比赛中击败了玩家 Loseri。
返回大小为 2 的列表答案#xff0c;其中#xff1a;
answer[0] 是所有未输掉任何比赛的玩家的列表。answer[1] 是仅输掉一场比赛的…题目要求
给定一个整数数组 matches其中 matches[i] [winneri, Loseri] 表示玩家 Winneri 在一场比赛中击败了玩家 Loseri。
返回大小为 2 的列表答案其中
answer[0] 是所有未输掉任何比赛的玩家的列表。answer[1] 是仅输掉一场比赛的所有玩家的列表。
两个列表中的值应按升序返回。
您应该只考虑至少参加过一场比赛的球员。
生成的测试用例不会有任何两个匹配具有相同的结果。
Example 1:
Input: matches [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] [1,2,10] and answer[1] [4,5,7,8].Example 2:
Input: matches [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] [1,2,5,6] and answer[1] [].
思路 先把参与比赛的队伍的list得到然后用哈希表统计输的次数如果哈希表中的队伍没有出现在全部list中则是全胜的。然后再统计只输一场的即可。
代码
class Solution {
public:vectorvectorint findWinners(vectorvectorint matches) {vectorvectorint res(2);// 统计不重复的队伍用到setsetint teams;mapint, int losses;for (auto match : matches) {teams.insert(match[0]);teams.insert(match[1]);losses[match[1]];}for (int team : teams) {if (losses.find(team) losses.end()) {res[0].push_back(team);} else if (losses[team] 1) {res[1].push_back(team);}}sort(res[0].begin(), res[0].end());sort(res[1].begin(), res[1].end());return res;}
};
时间复杂度
遍历每场比赛的主循环的时间复杂度为 O(N)其中 N 为比赛场次。 查找无失利或正好有一场失利的球队的循环复杂度为 O(T)其中 T 是唯一球队的数量。 对于 res 中的两个子向量排序功能的复杂度均为 OT log T。 总的来说时间复杂度约为 O(N T log T)。 空间复杂度
空间复杂度主要取决于存储团队和失利队伍映射所需的空间。 Map和Set共需要 O(T) 个空间其中 T 是唯一球队的数量。 结果向量需要额外的空间但不会超过 O(T)。 因此总的空间复杂度为 O(T)。
