推 DJYOMIYAHINA: 大師 07/29 13:50
推 sustainer123: 大師 07/29 14:37
推 oin1104: 大師 07/29 14:59
推 Rushia: 我只會n^2的解 哀 07/29 15:29
※ 編輯: dont (185.213.82.66 臺灣), 07/29/2024 15:46:25
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
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.125 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722231472.A.4A5.html