※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 這題好像 水蠻深的 做法很多
: 自己是先用了個O(N^2) 先能過吧
: 直覺是想應該可以O(NlogN)啦
: 畢竟unique rating
: 隨便一個binary search方法應該都可以 但懶想
: 先去上班晚上再來看看其他人的寫法
: 我這應該就算brute force吧
: 大概就是
: 先init各rating後有多少rating是比他大的 全記下來
: 然後就forloop加加加加加
: 最後反過來再做一次 對ㄚ==
: def numTeams(self, rating: List[int]) -> int:
: n = len(rating)
: def helper(rating):
: ushiros = defaultdict(list)
: for i in range(n):
: cnt_cur = 0
: for j in range(i, n):
: if rating[j] > rating[i]:
: ushiros[rating[i]].append(rating[j])
: ans = 0
: for num in rating:
: for num2 in ushiros[num]:
: ans += len(ushiros[num2])
: return ans
: return helper(rating) + helper(rating[::-1])
思路:
看解答 姆咪
這思路也是暴力解 晚點看一下有沒有其他方法
Python Code:
class Solution:
def numTeams(self, rating: List[int]) -> int:
asc = dsc = 0
for i, v in enumerate(rating):
llc = lgc = rlc = rgc = 0
for l in rating[:i]:
if l > v:
lgc += 1
elif l < v:
llc += 1
for r in rating[i+1:]:
if r > v:
rgc += 1
elif r < v:
rlc += 1
asc += llc * rgc
dsc += lgc * rlc
return asc + dsc