※ 引述《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