文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
**解析：**Version 1，暴力比较，三重循环，超时。Version 2，如果把每个数作为三个数的中间数值，则每个数对应的团队数量为其左边小于它的数字个数乘以右边大于它的数字个数加上其左边大于它的数字个数乘以右边小于它的数字个数。Version 3是Version 2的另一种形式。
- Version 1
class Solution:def numTeams(self, rating: List[int]) -> int:count = 0n = len(rating)for i in range(n):for j in range(i+1, n):for k in range(j+1, n):if rating[i] < rating[j] and rating[j] < rating[k]:count += 1elif rating[i] > rating[j] and rating[j] > rating[k]:count += 1return count
- Version 2
class Solution:def numTeams(self, rating: List[int]) -> int:count = 0n = len(rating)for i in range(n):greater_left = 0greater_right = 0less_left = 0less_right = 0for j in range(i):if rating[i] > rating[j]:less_left += 1else:greater_left += 1for j in range(i+1, n):if rating[i] > rating[j]:less_right += 1else:greater_right += 1count += greater_left * less_right + greater_right * less_leftreturn count
- Version 3
class Solution:def numTeams(self, rating: List[int]) -> int:count = 0n = len(rating)greater_left = collections.defaultdict(int)greater_right = collections.defaultdict(int)less_left = collections.defaultdict(int)less_right = collections.defaultdict(int)for i in range(n):for j in range(i+1, n):if rating[i] > rating[j]:less_right[i] += 1greater_left[j] += 1else:greater_right[i] += 1less_left[j] += 1for i in range(n):count += greater_left[i] * less_right[i] + greater_right[i] * less_left[i]return count
Reference
- https://leetcode.com/problems/count-number-of-teams/