1395. Count Number of Teams
## 思路
两层for循环,
第一层 j
第二层分别往左右找 (i,j) (j,k) 的配对数 再相乘
## Complexity
Time: O(N^2)
Space: O(1)
## Code
```python
class Solution:
def numTeams(self, rating: List[int]) -> int:
n = len(rating)
ans = 0
for j in range(n):
left_incr = left_desc = right_incr = right_desc = 0
for i in range(j):
if rating[i] > rating[j]:
left_desc += 1
elif rating[i] < rating[j]:
left_incr += 1
for k in range(j+1, n):
if rating[j] > rating[k]:
right_desc += 1
elif rating[j] < rating[k]:
right_incr += 1
ans += (left_incr * right_incr) + (left_desc * right_desc)
return ans
```
瞄了一下答案 最佳解是Bit indexed tree
Time: O(N log(max rating))
Space: O(max rating)
建两个size是max(rating)的BIT
left_bit 每次塞1到index=r
get_sum(r-1) 跟 j-get_sum 分别可得到递增/减的 (i, j) 配对数
right_bit 则是先塞完rating, 再逐次扣掉index=r
get_sum(r-1) 跟 (n-j-1)-get_sum 则是 (j,k) 配对数
```python
class BIT:
def __init__(self, n):
self.bits = [0] * (1+n)
self.size = n
def update(self, idx, val):
idx += 1
while idx <= self.size:
self.bits[idx] += val
idx += (idx & -idx)
def get_sum(self, idx):
idx += 1
res = 0
while idx > 0:
res += self.bits[idx]
idx -= (idx & -idx)
return res
class Solution:
def numTeams(self, rating: List[int]) -> int:
n = len(rating)
ans = 0
left_bit = BIT(max(rating))
right_bit = BIT(max(rating))
for r in rating:
right_bit.update(r, 1)
for j, r in enumerate(rating):
right_bit.update(r, -1)
left_bit.update(r, 1)
left_incr = left_bit.get_sum(r-1)
left_desc = j - left_incr
right_desc = right_bit.get_sum(r-1)
right_incr = (n - j - 1) - right_desc
ans += (left_incr * right_incr) + (left_desc * right_desc)
return ans
```