Re: [閒聊] 每日leetcode
只想到硬幹 O(N^2)
不過可以把每次pair檢查壓到O(1)
x從小排到大 同x的從大排到小
每次往比自己x大的檢查
每一輪固定A loopB時
隨時記下在A右下的點之中最上面的B
當你loop到的B點的y值比它小
代表它一定在你們中間
好饒口= =
def numberOfPairs(self, points: List[List[int]]) -> int:
points.sort(key=lambda p: (p[0], -p[1]))
rets = 0
n = len(points)
for i in range(n):
a_x, a_y = points[i][0], points[i][1]
cur_max_b_y = -1
for j in range(i+1, n):
b_x, b_y = points[j][0], points[j][1]
if b_y<=a_y:
if b_y>cur_max_b_y:
rets += 1
cur_max_b_y = max(cur_max_b_y, b_y)
return rets
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1756828624.A.5C2.html
※ 編輯: DJYOMIYAHINA (220.132.58.28 臺灣), 09/02/2025 23:57:59
討論串 (同標題文章)
完整討論串 (本文為第 1511 之 1548 篇)：