Leetcode 1395. Count Number of Teams

文章作者：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 = 0
        n = 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 += 1
                    elif rating[i] > rating[j] and rating[j] > rating[k]:
                        count += 1
        return count

• Version 2

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        n = len(rating)
        for i in range(n):
            greater_left = 0
            greater_right = 0
            less_left = 0
            less_right = 0
            for j in range(i):
                if rating[i] > rating[j]:
                    less_left += 1
                else:
                    greater_left += 1
            for j in range(i+1, n):
                if rating[i] > rating[j]:
                    less_right += 1
                else:
                    greater_right += 1
            count += greater_left * less_right + greater_right * less_left
        return count

• Version 3

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        count = 0
        n = 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] += 1
                    greater_left[j] += 1
                else:
                    greater_right[i] += 1
                    less_left[j] += 1
        for i in range(n):
            count += greater_left[i] * less_right[i] + greater_right[i] * less_left[i]
        return count

Reference

1. https://leetcode.com/problems/count-number-of-teams/