Leetcode 1395. Count Number of Teams

1. Description

2. Solution

**解析：**Version 1，暴力比较，三重循环，超时。Version 2，如果把每个数作为三个数的中间数值，则每个数对应的团队数量为其左边小于它的数字个数乘以右边大于它的数字个数加上其左边大于它的数字个数乘以右边小于它的数字个数。Version 3是Version 2的另一种形式。

• Version 1

代码语言：javascript复制

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

代码语言：javascript复制

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

代码语言：javascript复制

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/

version

0 人点赞