Re: [閒聊] 每日leetcode

看板Marginalman作者 (通通打死)時間1年前 (2024/11/13 23:10), 1年前編輯推噓2(2推 0噓 2→)
留言4則, 3人參與, 1年前最新討論串1119/1548 (看更多)
用一堆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
推
11/13 23:40, 1年前 , 1F
大師
11/13 23:40, 1F
推
11/13 23:49, 1年前 , 2F
也可以先把nums排序後 對[i+1,n) 兩次做binary search
11/13 23:49, 2F
→
11/13 23:49, 1年前 , 3F
idx_r = bisect.bisect_right(nums, upper-nums[i], i+1)
11/13 23:49, 3F
→
11/14 14:43, 1年前 , 4F
大師
11/14 14:43, 4F
‣ 更多 DJYOMIYAHINA 的文章
文章代碼(AID): #1dDC5enb (Marginalman)
討論串 (同標題文章)
完整討論串 (本文為第 1119 之 1548 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共1548篇)
‣ 更多 DJYOMIYAHINA 的文章
文章代碼(AID): #1dDC5enb (Marginalman)