推 oin1104: 大師 11/13 23:40
推 dont: 也可以先把nums排序後 對[i+1,n) 兩次做binary search 11/13 23:49
→ dont: idx_r = bisect.bisect_right(nums, upper-nums[i], i+1) 11/13 23:49
→ DJYOMIYAHINA: 大師 11/14 14:43
用一堆bisect function可以過
但其實insort是O(N) 所以這樣是O(N^2)
想當然是墊底
看答案
原來先sort+two pointer也行
我好笨
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
traveled = []
ans = 0
for num in nums:
idx_r = bisect_right(traveled, upper-num)
idx_l = bisect_left(traveled, lower-num)
ans += (idx_r-idx_l)
insort(traveled, num)
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731510632.A.C65.html
※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 11/13/2024 23:11:50